【LeetCode每日一题】1944. 队列中可以看到的人数（单调栈）

2024-01-08 15:36:45

2024-1-5

文章目录

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

在这里插入图片描述

在这里插入图片描述

思路：

1.采用单调栈，从最后一个高度开始，从后往前进行遍历

2.用一个循环，先解决比当前低的身高

3.因为栈不为空且栈顶比现在身高低，当前身高把栈顶身高挡住了，栈顶无法影响后续，弹出，记录看到的低栈顶

4.当前栈不为空，并且之前已经排除了比当前栈顶元素低的，所以当前栈顶元素比当前身高要高，记录看到的这个高的

5.每次循环，都对当前身高进行压栈，用来更新栈顶元素。

//1944. 队列中可以看到的人数---单调栈
    public int[] canSeePersonsCount(int[] heights) {

        int n = heights.length;
        Deque<Integer> stack = new ArrayDeque<>();
        int[]answer = new int[n];
        for (int i = n-1; i >=0 ; i--) {
            //int h = heights[i];
            while (!stack.isEmpty()&&stack.peek()<heights[i]){//
                //栈不为空且当前高度大于栈顶元素
                stack.pop();
                //当前高度把栈顶挡住了，栈顶出栈，看栈中的下一个元素
                answer[i]++;
                //看到了一个比当前低的，加1
            }
            if (!stack.isEmpty()){
                //栈不为空，当前高度小于栈顶元素
                answer[i]++;
                //只能看到栈顶，能看见一个比当前高的，加1
            }
            stack.push(heights[i]);
            //当前高度压栈
            
        }
        return answer;

    }

点击移步博客主页，欢迎光临~

偷cyk的图

文章来源:https://blog.csdn.net/m0_64003319/article/details/135408203
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。