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

提示：

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

分析

先思考如果暴力怎么做呢， 我们从前往后枚举每一个数，对于每一个数，再对后面的每个数进行枚举，维护一个最大值判断这个点是不是满足题目所示的条件，这样做的时间复杂度是$O(n^2)$，显然会超时，那么我们考虑优化，在枚举的过程中，如果发现如果出现第一个比当前枚举的数要大时，假定为x, 那么后面所有的值都是不能取到的，因为已经不能满足条件了，那么我们可以分析一下这个数x，怎么求这个数呢，单调栈可以实现，同时我们用这个数据结构可以将无用的数去掉，那么答案是什么呢，构建单调栈的时候，由于栈中的元素是单调的，我们每次弹出一个元素，那么我们答案就加上1，因为单调，并且这个数谈出去了，所以是满足题目的条件的，如果最后栈中还有元素，那么答案再次加1，比当前枚举的数大的数也是满足条件的

代码实现

cpp 版本

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

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

python3版本

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

时间复杂度同

结束了