队列中可以看到的人数
难度:
标签:
题目描述
有 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.length1 <= n <= 1051 <= heights[i] <= 105heights中所有数 互不相同 。
代码结果
运行时间: 100 ms, 内存: 29.5 MB
/*
* 思路：
* 类似于普通Java解法，这里我们使用Stream API来处理栈的操作。
* 我们会用一个ArrayDeque作为栈，记录尚未被挡住的身高。
* 通过IntStream来反向遍历heights数组，并使用collect方法收集结果。
*/
import java.util.*;
import java.util.stream.*;
public class Solution {
public int[] canSeePersonsCount(int[] heights) {
ArrayDeque<Integer> stack = new ArrayDeque<>();
return IntStream.range(0, heights.length)
.map(i -> heights.length - 1 - i)
.map(i -> {
int count = 0;
while (!stack.isEmpty() && stack.peek() < heights[i]) {
stack.pop();
count++;
}
if (!stack.isEmpty()) count++;
stack.push(heights[i]);
return count;
}).toArray();
}
}解释
方法:
这个问题可以通过单调栈来解决。从右向左遍历数组，使用一个单调递减栈来存储遇到的元素。对于每个元素，如果栈顶元素比当前元素矮，则弹出栈顶元素，并且计数加1，这表示当前元素可以看到这些被弹出的元素。如果遇到一个比当前元素高的人，则停止弹出，并将当前元素入栈，因为此时当前元素只能看到栈中剩余的最近的一个比它高的人。最后，如果栈中没有比当前元素高的人，说明当前元素可以看到所有弹出的元素；如果栈中有比当前元素高的人，当前元素能看到的人数要减去最后一个未被看到的人（因为它被看到的计数被提前1计算了）。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么单调栈是解决这个问题的合适数据结构？
▷🦆
在单调栈的处理过程中，为何一旦遇到栈顶元素比当前元素矮就需要将其弹出？
▷🦆
在算法中，如何确保`min(heights[i], heights[j]) > max(heights[i+1], ..., heights[j-1])`这一条件得到满足？
▷🦆
如果数组中存在相同高度的人会怎样影响算法的执行和结果？
▷