【leetcode：1944. 队列中可以看到的人数】单调栈算法及其相关问题

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

题目

有?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?个人在他右侧队列中能?看到?的?人数?。

原始想法

• 对于序号为i的人，右侧第一个高度大于等于他的人序号为j，那么j右侧的人，i一定无法看到了。
• 那只需要判断i和j之间的人

“右侧第一个高度大于等于他的人”，这句话让人很自然的想到单调栈，因为单调栈的常见适用场景就是寻找左（右）侧第一个比当前元素大（小）的元素。

利用单调栈找到i右侧第一个高度大于等于他的j后，如何判断i是否能看到中间的某个人k呢？按照题目描述，i和k之间的所有人都比他们两人矮，这用遍历就能解决，但时间复杂度显然比较高，有没有办法优化一下？

可以再利用单调栈，寻找每个人左侧第一个高度大于等于他的人，如果k左边第一个高度大于等于他的人位置小于等于i，说明i和k之间的人高度都小于他们，也就是满足题目中被看到的条件。

总之，最终的思路是：

• 利用单调栈，找到每个人左边和右边第一个高度大于等于他的人，
  • 假设l[i]表示i左侧第一个高度大于等于他的人的位置，r[i]表示i右侧第一个高度大于等于他的人的位置
• 对于i来说，遍历i和r[i]之间的所有元素，比如i < k ≤ r[i]，如果l[k] ≤ i，那么i就能看到k。

代码如下：

class Solution {
public:
    vector<int> canSeePersonsCount(vector<int>& heights) {
        int len = heights.size();
        stack<int> sl = stack<int>();
        stack<int> sr = stack<int>();
        vector<int> l = vector<int>(len, -1); // 左边第一个高度大于等于
        vector<int> r = vector<int>(len, len);
        // 利用单调栈寻找l
        for(int i = 0;i < len;++i) {
            while(!sl.empty() && heights[i] > heights[sl.top()]) {
                sl.pop();
            }
            l[i] = sl.empty() ? -1 : sl.top();
            sl.push(i);
        }
        // 利用单调栈寻找r
        for(int i = len - 1;i >= 0;--i) {
            while(!sr.empty() && heights[i] > heights[sr.top()]) {
                sr.pop();
            }
            r[i] = sr.empty() ? len : sr.top();
            sr.push(i);
        }
        
        vector<int> res(len, 0);
        for(int i = 0;i < len - 1;++i) {
            int j = i + 1;
            for(;j < r[i];++j) {
                if(l[j] <= i) {
                    ++res[i];
                }
            }
            if(j != len) {
                ++res[i];
            }
        }
        return res;
    }
};

利用单调栈计算l和r的时间复杂度是$O(n)$，针对每个人又遍历判断是否满足“看到”的要求，所以总体时间复杂度是$O(n^2)$ 。提交结果是对于某些情况超时，说明这种解决方案的时间复杂度还是太高了。

问题出在哪里呢？

最终方案

深究利用单调栈计算l（r）的过程：对于某个元素i，如果栈顶元素高度小于i的高度，就把栈顶元素弹出，直到栈顶元素高度大于等于他的高度或者栈空。元素i入栈

这个过程中，弹出的元素和元素i之间一定满足“两者之间的元素高度都小于两者”，否则当前栈顶元素在之前就会被出栈。

所以，其实在上述过程中弹出的元素就是i能够看到的人，因此原始想法中的遍历过程是重复计算的。

最终代码如下：

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

这样时间复杂度其实就只有$O(n)$了，理所应当地通过了。

单调栈知识点及相关题目

单调栈知识点可以参考：https://oi-wiki.org/ds/monotonous-stack/

leetcode上其实有很多单调栈相关题目，比如剑指 Offer II 039. 直方图最大矩形面积等。