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

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

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

n个人排成一个队列,从左到右编号为0n - 1。给你以一个整数数组heights,每个整数互不相同heights[i]表示第i个人的高度。

一个人能看到他右边另一个人的条件是这两人之间的所有人都比他们两人。更正式的,第i个人能看到第j个人的条件是i < jMIN(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;
}
相关文章
LeetCode 热题100——单调栈
LeetCode 热题100——单调栈
17 0
|
1月前
|
Go C++
【力扣】2696. 删除子串后的字符串最小长度(模拟 栈 C++ Go实现栈)
【2月更文挑战第18天】2696. 删除子串后的字符串最小长度(模拟 栈 C++ Go实现栈)
32 6
|
3月前
【Leetcode 2487】从链表中移除节点 —— 单调栈
解题思路:维持一个单调递增栈,当栈为空时,记录当前节点为头节点;否则当前节点为栈顶节点的后继节点
|
1月前
|
存储
leetcode1944. 队列中可以看到的人数
leetcode1944. 队列中可以看到的人数
15 0
|
1月前
|
算法 安全 Java
【数据结构与算法】6、栈(Stack)的实现、LeetCode:有效的括号
【数据结构与算法】6、栈(Stack)的实现、LeetCode:有效的括号
21 0
|
3月前
|
容器
代码随想录 Day49 单调栈01 LeetCode LeetCodeT739每日温度 T496 下一个最大元素I
代码随想录 Day49 单调栈01 LeetCode LeetCodeT739每日温度 T496 下一个最大元素I
29 0
|
3月前
代码随想录Day29 贪心04 LeetCode T860 柠檬水找零 T406 根据身高重建队列 T452 用最少得箭引爆气球
代码随想录Day29 贪心04 LeetCode T860 柠檬水找零 T406 根据身高重建队列 T452 用最少得箭引爆气球
25 0
|
19天前
|
机器学习/深度学习 算法
力扣刷题日常(一)
力扣刷题日常(一)
19 2
|
1月前
|
存储 索引
《LeetCode》—— LeetCode刷题日记
《LeetCode》—— LeetCode刷题日记
|
1月前
|
搜索推荐
《LeetCode》——LeetCode刷题日记3
《LeetCode》——LeetCode刷题日记3