【每日一题】队列中可以看到的人数

Tag

【单调栈】【数组】【2024-01-05】

---

题目来源

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

---

解题思路

方法一：单调栈

思路

暴力枚举的方法需要枚举 heights 中每一个高度 heights[i] 右侧的高度 heights[j]，一一计算从高度 heights[i] 可以看到的 heights[j] 的数量。时间复杂度为 $O(n^2)$，对于本题的数据量必然超时。

考虑如何优化。在暴力枚举中存在一些无用的操作，如果 heights[i] 和 heights[j] 之间有一堵墙，即有：

$$heights[k]>height[j],?k\in (i,j)$$

我们从右往左遍历 heights，使用单调栈来记录没有被墙挡住的高度。如果发现一个 heights[k] 比右边的高度 heights[j] 大，那么 k 左侧的人就再也看不到 j 了。

算法

从右往左遍历 heights，对于当前位置 i，如果高度比栈顶元素大，那么当前位置可以看到栈顶的元素，res[i] ++，如此迭代更新 res[i]，直至栈为空或当前高度不大于此时的栈顶元素。

出栈结束后，若栈不为空，说明第 i 个人还可以再看到一个人（栈顶），更新 res[i] ++。

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

复杂度分析

时间复杂度：$O(n)$，$n$ 为数组 heights 的长度。每个高度至多入栈出栈一次。

空间复杂度：$O(n)$。

---

写在最后

如果您发现文章有任何错误或者对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度的方法，欢迎评论区交流。

最后，感谢您的阅读，如果有所收获的话可以给我点一个 👍 哦。