leetcode在力扣 App 中打开
调试中...
调试中...
题目描述
题目描述
题解
题解
提交记录
提交记录
代码
代码
测试用例
测试用例
测试结果
测试结果
困难
相关标签
相关企业
提示

有 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 中所有数 互不相同 。
通过次数
25.6K
提交次数
37K
通过率
69.1%

相关标签

相关企业

提示 1
How to solve this problem in quadratic complexity ?

提示 2
For every subarray start at index i, keep finding new maximum values until a value larger than arr[i] is found.

提示 3
Since the limits are high, you need a linear solution.

提示 4
Use a stack to keep the values of the array sorted as you iterate the array from the end to the start.

提示 5
Keep popping from the stack the elements in sorted order until a value larger than arr[i] is found, these are the ones that person i can see.


评论 (0)

贡献者
© 2025 领扣网络(上海)有限公司
0 人在线
行 1,列 1
运行和提交代码需要登录
heights =
[10,6,8,5,11,9]
Source