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

本文主要是介绍leetcode1944. 队列中可以看到的人数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

文章目录

题目
解题方法
复杂度
Code

题目

有 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 中所有数
互不相同

。

解题方法

使用单调栈，因为题目要求是i往右边看，所以我们从右往左遍历，使用一个单调递减的栈去保存已经遍历过的数字。

对于当前元素，如果栈顶元素小于当前元素，说明栈顶元素肯定能被看见，答案加1，并且弹出他。这里我们为什么要弹出他呢？因为这个元素比当前元素小，所以当前元素左边的数不会看到他，所以要弹出

在弹出的操作结束后，如果这个栈不为空的，说明右边存在一个元素大于等于当前元素，这个元素也可以被看见，所以我们答案加1
最终我们添加当前元素到栈中

复杂度

时间复杂度:

只遍历一遍，所以是 $O (n)$

空间复杂度:

只用stack存储元素，极端情况下会存储n个数字，所以是 $O (n)$

Code

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