LeetCode1944. 队列中可以看到的人数，单调栈,逆序遍历

一、题目

1、题目描述

有?n?个人排成一个队列，从左到右?编号为?0?到?n - 1?。给你以一个整数数组?heights?，每个整数?互不相同，heights[i]?表示第?i?个人的高度。

一个人能?看到?他右边另一个人的条件是这两人之间的所有人都比他们两人?矮?。更正式的，第?i?个人能看到第?j?个人的条件是?i < j?且?min(heights[i], heights[j]) > max(heights[i+1], heights[i+2], ..., heights[j-1])?。

请你返回一个长度为?n?的数组?answer?，其中?answer[i]?是第?i?个人在他右侧队列中能?看到?的?人数?。

2、接口描述

?

class Solution {
public:
    vector<int> canSeePersonsCount(vector<int>& heights) {

    }
};

3、原题链接

1944. 队列中可以看到的人数

二、解题报告

1、思路分析

不难发现一个人能看到的为其右边的单调递增子序列，且子序列中至多只有最后一个人比他高

那么可以维护一个单调栈，但是我们发现我们正向遍历维护单调栈会很困难，既要找到递增子序列又要维护递减栈，所以我们逆向遍历，这样只需要维护一个单调递减栈，每个人能看到的人就是左边比他小的矮，如果左边有比他高的人，那么再+1

2、复杂度

时间复杂度：O(n) 空间复杂度：O(n)

3、代码详解

?

class Solution {
public:
    vector<int> canSeePersonsCount(vector<int>& heights) {
        stack<int> s;
        vector<int> ret(heights.size());
        int n = heights.size();
        for(int i = n - 1 ; i >= 0 ; i--)
        {
            while(s.size() && heights[i] > heights[s.top()])
                ret[i] += 1 , s.pop();
            ret[i] += !s.empty();
            s.emplace(i);
        }

        return ret;
    }
};