技术网站,域名iis网站添加,南通网站搭建定制,开发型网站报价方法文章目录 队列中可以看到的人数题目描述问题分析程序代码#xff08;Golang 版本#xff09; 队列中可以看到的人数
题目描述 原题链接 有 n 个人排成一个队列#xff0c;从左到右 编号为 0 到 n - 1 。给你以一个整数数组 heights #xff0c;每个整数 互不相同#xff… 文章目录 队列中可以看到的人数题目描述问题分析程序代码Golang 版本 队列中可以看到的人数
题目描述 原题链接 有 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 个人在他右侧队列中能 看到 的 人数 。
问题分析
从左往右看高的人会把矮的人挡住只能看到右边呈现一个单调递增的序列因此考虑使用单调栈求解该问题。
假设i j则i看到景象包含了j所看到的景象若j挡住了后面所有的人则信息蕴含在j本身。因此从子问题求解的角度分析单调栈求解该问题应该从右往左进行遍历。
记遍历过程中当前要研究的对象为i其对应的高度为h。单调栈此时维持的是i右边所可能看到的对象单调递增的序列。统计单调栈中比i矮的人数i能看到的人数并弹出栈因为在i前面的人看不到这些人会被i挡住。
最后判断此时栈是否为空若不为空要再加上i所能看到的最后一个人即第一个比i要高的人。然后将i压入栈中。
程序代码Golang 版本
func canSeePersonsCount(heights []int) []int {n : len(heights)res : make([]int, n)stk : make([]int, 0)for i : n - 1; i 0; i-- {h : heights[i]for len(stk) 0 stk[len(stk) - 1] h {stk stk[:len(stk)-1]res[i]}if len(stk) 0 {res[i];}stk append(stk, h)}return res
}
