企业官方网站系统建设,怎么样让网站网址有图标,景安做网站教程,浙江住房和城乡建设部网站上一篇:算法随笔_57 : 游戏中弱角色的数量-CSDN博客 题目描述如下:
有 n 个人排成一个队列#xff0c;从左到右 编号为 0 到 n - 1 。给你以一个整数数组 heights #xff0c;每个整数 互不相同#xff0c;heights[i] 表示第 i 个人的高度。
一个人能 看到 他右边另一个人…上一篇:算法随笔_57 : 游戏中弱角色的数量-CSDN博客 题目描述如下:
有 n 个人排成一个队列从左到右 编号为 0 到 n - 1 。给你以一个整数数组 heights 每个整数 互不相同heights[i] 表示第 i 个人的高度。
一个人能 看到 他右边另一个人的条件是这两人之间的所有人都比他们两人 矮 。更正式的第 i 个人能看到第 j 个人的条件是 i j 且 min(heights[i], heights[j]) max(heights[i1], heights[i2], ..., 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[i1]所以肯定res[i]1除了res[-1]。
3. heights[i]如果想看到heights[i2]heights[i3]等需要heights[i] heights[i1] heights[i2] heights[i3].....。
此时我们应该就发现了规律我们可以维护一个栈结构来计算出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_lenlen(heights)stck[heights[-1]]res[0]*h_lenfor i in range(h_len-2,-1,-1):cnt0while stck and heights[i] stck[-1]:stck.pop()cnt1res[i]cnt1 if stck else cntstck.append(heights[i])return res
关键词: 单调栈
