LeetCode 1944.队列中可以看到的人数：（一步步图解）单调栈

【LetMeFly】1944.队列中可以看到的人数：（一步步图解）单调栈

力扣题目链接：https://leetcode.cn/problems/number-of-visible-people-in-a-queue/

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

?

示例 1：

输入：heights = [10,6,8,5,11,9]
输出：[3,1,2,1,1,0]
解释：
第 0 个人能看到编号为 1 ，2 和 4 的人。
第 1 个人能看到编号为 2 的人。
第 2 个人能看到编号为 3 和 4 的人。
第 3 个人能看到编号为 4 的人。
第 4 个人能看到编号为 5 的人。
第 5 个人谁也看不到因为他右边没人。

示例 2：

输入：heights = [5,1,2,3,10]
输出：[4,1,1,1,0]

?

提示：

• n == heights.length
• 1 <= n <= 105
• 1 <= heights[i] <= 105
• heights?中所有数 互不相同?。

方法一：单调栈

思路

使用一个单调递减（非递增）栈，从栈底到栈顶是越来越矮的人。

从右往左遍历身高序列，当栈顶元素小于自己时（自己可以看到这个人，并且视线不被其阻挡，自己左边的人由于自己将无法看到这人），将这人出栈，自己看到的人的个数加一。

然后自己入栈。在自己入栈前，若栈中有人（那一定比自己高）则自己能看到的人数再加一。

举例

假设身高队列为3, 4, 1, 2, 8：

    3 4 1 2 8    ]
ans:0 0 0 0 0

栈中无比8低之人，8入栈：

    3 4 1 2     8]
ans:0 0 0 0     0

栈中无比2低之人，2入栈（入栈时栈非空，2能看到8）

    3 4 1     2 8]
ans:0 0 0     1 0

栈中无比1低之人，1入栈（入栈时栈非空，1能看到2）

    3 4     1 2 8]
ans:0 0     1 1 0

栈中1、2都比4低（4能看到1、2），1、2出栈4入栈（入栈时栈非空，4能看到8）

    3     4 8]
ans:0     3 0

栈中无比3低之人，3入栈（入栈时栈非空，3能看到4）

        3 4 8]
ans:    1 3 0

终止。3, 4, 1, 2, 8能看到的人数分别为1, 3, 1, 1, 0。

• 时间复杂度$O(len(heights))$
• 空间复杂度$O(len(heights))$

AC代码

C++

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

Python

# from typing import List

class Solution:
    def canSeePersonsCount(self, heights: List[int]) -> List[int]:
        ans = [0] * len(heights)
        st = []
        for i in range(len(heights) - 1, -1, -1):
            while st and heights[st[-1]] < heights[i]:
                st.pop()
                ans[i] += 1
            if st:
                ans[i] += 1
            st.append(i)
        return ans

同步发文于CSDN，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/135416441