leetcode1944. 队列中可以看到的人数
Problem: 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 个人在他右侧队列中能 看到 的 人数 。
示例 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 ) O(n) O(n)
空间复杂度:
只用stack存储元素,极端情况下会存储n个数字,所以是 O ( n ) O(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]+=1
if stack:
ans[i]+=1
stack.append(heights[i])
return ans
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!