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

本文主要是介绍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] * nfor i in range(n - 1, -1, -1) :print(i)while stk and stk[-1] < heights[i] :stk.pop()res[i] += 1if stk : res[i] += 1stk.append(heights[i])return res