【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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。