算法每日一题：队列中可以看到的人数 | 单调栈

大家好，我是星恒
今天是一道困难题，他的题解比较好理解，但是不好想出来，接下来就让我带大家来捋一捋这道题的思路，以及他有什么特征

题目：leetcode 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 <= 105
• 1 <= heights[i] <= 105
• heights 中所有数 互不相同 。

分析：
看到这道题，大家第一想到的一定是枚举每一种情况，然后依次与每一个值比较，记录比当前值大的值；当然，他的时间复杂度是O(n2)，他的作用只能是为我们提供一些信息：
最大都是O(n2)，说明优化大概率是O(n) 或者 O(nlogn)；我们可以想到的方法，二分？利用一些特殊的数据结构？动归？等等。很明显这道题不能使用二分，因为没有折半的判断条件呀！所以我们可以拓展其他思维

从题目中的例子可以看出，对于某个人，他可以看到 比它小的人，并且这些人的规律是 单调递增，ok，看到单调性，我们肯定能想到这个数据结构：单调栈，没错，这道题的思路就是单调栈，但难点就在如何使用单调栈：

由于前面的看到的是一个单调递增的序列，并且我们需要从后向前来维护，所以我们维护一个从栈底到栈顶递减的一个栈。
同样，由于前面的人，看不到被后面的人挡住的比其（后面的这个人）小的人，即使这个人比它小，所以我们可以直接把他抛弃掉，这样前面的人只要将栈里面比它小的人统计，就可以知道它可以看多少人了，当然，统计后出栈即可，因为它挡住了前面的视线（看比它小的人的视线）

题解：

class Solution {
    public int[] canSeePersonsCount(int[] heights) {
        int n = heights.length;
        Deque<Integer> stack = new ArrayDeque<Integer>();
        int[] res = new int[n];

        for (int i = n - 1; i >= 0; i--) {
            int h = heights[i];
            while (!stack.isEmpty() && stack.peek() < h) {
                stack.pop();
                res[i]++;
            }
            if (!stack.isEmpty()) {
                res[i]++;
            }
            stack.push(h);
        }
        return res;
    }
}

如果大家有什么思考和问题，可以在评论区讨论，也可以私信我，很乐意为大家效劳。
好啦，今天的每日一题到这里就结束了，如果大家觉得有用，可以可以给我一个小小的赞呢，我们下期再见！

这里和大家说声不好意思，这周从元旦开始都没有发帖子，尤其每日一题，对不起！
原因是这今天都计划上午写贴子，晚上发贴子，但是由于这几天回了家里，稍微有点忙，并且和在学校相比，有些许不适应，所以一直没有顾上发，但其实我每天都在坚持写，今天我们把我这周攒下的每日一题都发出来了，大家感兴趣的可以去看看，让我们一起进步 ~~~