【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;
}
相关文章
|
1月前
【LeetCode 24】225.用队列实现栈
【LeetCode 24】225.用队列实现栈
12 0
|
1月前
|
算法
【LeetCode 23】232.用栈实现队列
【LeetCode 23】232.用栈实现队列
18 0
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 30. 包含min函数的栈
本文提供了实现一个包含min函数的栈的Python代码,确保min、push和pop操作的时间复杂度为O(1)。
28 4
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 09. 用两个栈实现队列
使用两个栈实现队列的Python解决方案,包括初始化两个栈、实现在队列尾部添加整数的appendTail方法和在队列头部删除整数的deleteHead方法,以及相应的示例操作。
39 2
|
3月前
|
Python
【Leetcode刷题Python】641.循环双端队列
文章介绍了如何实现一个循环双端队列,包括其操作如插入、删除、获取队首和队尾元素,以及检查队列是否为空或已满,并提供了Python语言的实现代码。
24 0
|
3月前
|
Python
【Leetcode刷题Python】232. 用栈实现队列
如何使用Python语言通过两个栈来实现队列的所有基本操作,包括入队(push)、出队(pop)、查看队首元素(peek)和判断队列是否为空(empty),并提供了相应的代码实现。
21 0
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
57 6
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
114 2
|
21天前
|
机器学习/深度学习 人工智能 自然语言处理
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
16 1