1944. Number of Visible People in a Queue

Description

Solution

Using monotone stack, look into preceding first number larger than current one.

Code

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--){
            while(!stk.empty() && stk.top() < heights[i]){
                res[i]++;
                stk.pop();
            }
            if(!stk.empty())
                res[i]++;
            stk.push(heights[i]);
        }
        return res;
    }
};