Monotonic queue

A 4th question of Biweekly LeetCode contest.

1944. Number of Visible People in a Queue

We can use a monotonic queue to solve this problem.

class Solution {
public:
    vector<int> canSeePersonsCount(vector<int>& heights) {
        const int n = heights.size();
        vector<int> ret(n);
        vector<int> q;
        for (int i = n - 1; i >=0; --i){
            while (!q.empty() && heights[i] > q.back()){
                ret[i]++;
                q.pop_back();
            }
            if (!q.empty())ret[i]++;
            q.push_back(heights[i]);
        }
        return ret;
    }
};