LC.P1944[队列中可以看到的人数]

方法一：单调栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int[] canSeePersonsCount(int[] heights) {
        int n = heights.length;
        int[] ans = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = n - 1; i >= 0; --i) {
            while (!stack.isEmpty() && stack.peek() < heights[i]) {
                stack.pop();
                ans[i]++;
            }
            if (!stack.isEmpty()) {
                ans[i]++;
            }
            stack.push(heights[i]);
        }
        return ans;
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$

方法二：数组实现单调栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int[] canSeePersonsCount(int[] heights) {
        int n = heights.length, tt = -1;
        int[] ans = new int[n], stack = new int[n];
        for (int i = n - 1; i >= 0; --i) {
            while (tt > -1 && stack[tt] < heights[i]) {
                --tt;
                ans[i]++;
            }
            if (tt > -1) {
                ans[i]++;
            }
            stack[++tt] = heights[i];
        }
        return ans;
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$