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]

提示：

• n == heights.length
• 1 <= n <= 1e5
• 1 <= heights[i] <= 1e5
• heights 中所有数 互不相同 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/number-of-visible-people-in-a-queue
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

做题结果

成功，但是写了5个小时。单调栈是考验思路的题【虽然结构固定】，依靠蒙是很难准的。最后一次正确也是思路终于正确了。

方法：单调栈

1. 单调递减栈

2. 如果存在前面的节点比当前节点大（单调栈小元素出栈后非空），则说明前面这个节点位置可以看到当前节点，对应前面的位置加1

3. 从后到前求最大值，如果当前位置不是最大值，则向右一定可以看到最大值，则对应位置加1

 class Solution {
        public int[] canSeePersonsCount(int[] heights) {
            int n = heights.length;
            int[] ans = new int[n];
            Stack stack = new Stack<>();
            for(int i = 0; i 
                while(!stack.isEmpty()&&heights[stack.peek()]
                    stack.pop();
                }
                if(!stack.isEmpty()) ans[stack.peek()]++;
                stack.push(i);
            }
 
            int max = 0;
            for(int i = n-1; i >= 0; i--){
                max = Math.max(heights[i],max);
                if(heights[i]
            }
            return ans;
        }
    }