【Leetcode 1944】队列中可以看到的人数 —— 单调栈

1944. 队列中可以看到的人数

有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]

题目分析

解题思路：

1. 维持一个单调递增栈来辅助计算每个人能够看到的人数。
2. 从右往左遍历数组，对于每个人，我们将其身高与栈顶元素的身高进行比较。如果当前人的身高比栈顶元素的身高高，则栈顶元素无法被当前人看到，将其出栈，并累计计数

单调递增栈：只有比栈顶元素小的元素才能直接进栈，否则需要先将栈中比当前元素小的元素出栈，再将当前元素入栈
单调栈详解及相关 Leetcode 题解见 Leetcode 单调栈详解

public int[] canSeePersonsCount(int[] heights) {
    int[] result = new int[heights.length];
    // 单调递增栈：辅助计算每个人能够看到的人数
    Deque<Integer> stack = new ArrayDeque<>();
    for(int i = heights.length - 1; i >= 0; i--){
        // 当栈不为空且当前人的身高比栈顶元素的身高高时，栈顶元素无法被当前人看到，出栈并累计计数
        while (!stack.isEmpty() && stack.peek() < heights[i]){
            stack.pop();
            result[i]++;
        }
        // 如果栈不为空，说明当前人能够看到栈顶元素，因此计数器需要加一
        if (!stack.isEmpty()) {
            result[i]++;
        }
        stack.push(heights[i]);
    }
    return result;
}