网站页面架构图长沙seo网站推广
上一篇:算法随笔_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关键词: 单调栈