Leetcode 1944. Number of Visible People in a Queue (单调栈好题)

1944. Number of Visible People in a Queue
      Hard

There are n people standing in a queue, and they numbered from 0 to n - 1 in left to right order. You are given an array heights of distinct integers where heights[i] represents the height of the ith person.

A person can see another person to their right in the queue if everybody in between is shorter than both of them. More formally, the ith person can see the jth person if i < j and min(heights[i], heights[j]) > max(heights[i+1], heights[i+2], …, heights[j-1]).

Return an array answer of length n where answer[i] is the number of people the ith person can see to their right in the queue.

Example 1:

Input: heights = [10,6,8,5,11,9]
Output: [3,1,2,1,1,0]
Explanation:
Person 0 can see person 1, 2, and 4.
Person 1 can see person 2.
Person 2 can see person 3 and 4.
Person 3 can see person 4.
Person 4 can see person 5.
Person 5 can see no one since nobody is to the right of them.
Example 2:

Input: heights = [5,1,2,3,10]
Output: [4,1,1,1,0]

Constraints:

n == heights.length
1 <= n <= 105
1 <= heights[i] <= 105
All the values of heights are unique.

解法1：单调栈
注意：

1. 因为是算往右看的人数，所以for循环必须从右往左。如果是从左往右的话，不知道右边会发生什么情况。
2. 从栈底到栈顶是单调递减。但如果按index递增的顺序来看，则res值是单调递增。
3. res[]里面存的是pop的count，也就是第i个item来的时候，能看到的往右的比它小的item。注意如果stk里面还有东西的话，count还要加1，即往右第一个比它大的数，否则就不用加1了，因为往右的item都比第i个item小。

class Solution {
public:
    vector<int> canSeePersonsCount(vector<int>& heights) {
        int n = heights.size();
        vector<int> res(n, 0);
        stack<int> stk;
        for (int i = n - 1; i >= 0; i--) {
            int count = 0;
            while (!stk.empty() && heights[stk.top()] < heights[i]) {
                count++;
                stk.pop();
            }
            res[i] = stk.size() == 0 ? count : count + 1;
            stk.push(i);
        }        
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18