算法随笔_58: 队列中可以看到的人数

上一篇:算法随笔_57 : 游戏中弱角色的数量-CSDN博客

=====

题目描述如下:

有 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 个人谁也看不到因为他右边没人。

=====

算法思路:

我们先设结果数组为res。索引-1，-2分别表示倒数第一个，倒数第二个元素。

我们从右往左观察一下原数组:

1. 由于heights[-1]右侧没有人，所以res[-1]等于0。

2. 紧挨着的两个人，heights[i]肯定能看到heights[i+1]，所以肯定res[i]>=1，除了res[-1]。

3. heights[i]如果想看到heights[i+2]，heights[i+3]等，需要heights[i] > heights[i+1] < heights[i+2] < heights[i+3].....。

此时我们应该就发现了规律，我们可以维护一个栈结构来计算出res。我们设数组stck为这个栈。初始值为stck=[heights[-1]]。

算法如下:

从右往左枚举原数组。只要heights[i]大于栈顶元素stck[-1]，就弹出stck[-1]，表示元素i 可以看到被弹出的这个元素。循环此判断，直到heights[i]小于stck[-1]，我们就把heights[i]放入stck。

对于单调栈来说，每个元素最多入栈和出栈各一次，所以时间复杂度为O(n)。下面是代码实现:

class Solution(object):def canSeePersonsCount(self, heights):""":type heights: List[int]:rtype: List[int]"""h_len=len(heights)stck=[heights[-1]]res=[0]*h_lenfor i in range(h_len-2,-1,-1):cnt=0while stck and heights[i] > stck[-1]:stck.pop()cnt+=1res[i]=cnt+1 if stck else cntstck.append(heights[i])return res

关键词: 单调栈