What pattern does 'Number of Visible People in a Queue' follow?

It follows a stack-based state management pattern where a monotonic stack tracks visibility to the right.

Can this problem be solved in O(n^2) time?

Yes, by checking every person to the right of each individual, but it is inefficient compared to the stack approach.

Why use a monotonic stack for this problem?

It efficiently counts visible people by maintaining order and popping shorter heights, reducing redundant comparisons.

How does GhostInterview help with this problem?

It guides implementation of the stack approach, prevents common pitfalls, and ensures linear time complexity.

What edge cases should I watch for?

Watch for tallest people at the end and consecutive increasing or decreasing heights, as these affect visibility counts.

#1944

Hard

auto_awesome栈·状态

LeetCode 题解工作台

队列中可以看到的人数

有 n 个人排成一个队列，从左到右编号为 0 到 n - 1 。给你以一个整数数组 heights ，每个整数互不相同， heights[i] 表示第 i 个人的高度。一个人能看到他右边另一个人的条件是这两人之间的所有人都比他们两人矮。更正式的，第 i 个人能看到第 j 个人的条件…

数组栈单调栈

题目描述

有 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 <= 10⁵
1 <= heights[i] <= 10⁵
heights 中所有数 互不相同 。

lightbulb

解题思路

方法一：单调栈

我们观察发现，对于第 $i$ 个人来说，他能看到的人一定是按从左到右高度严格单调递增的。

因此，我们可以倒序遍历数组 $\textit{heights}$ ，用一个从栈顶到栈底单调递增的栈 $\textit{stk}$ 记录已经遍历过的人的高度。

对于第 $i$ 个人，如果栈不为空并且栈顶元素小于 $\textit{heights}[i]$ ，累加当前第 $i$ 个人能看到的人数，然后将栈顶元素出栈，直到栈为空或者栈顶元素大于等于 $\textit{heights}[i]$ 。如果此时栈不为空，说明栈顶元素大于等于 $\textit{heights}[i]$ ，那么第 $i$ 个人能看到的人数还要再加 $1$ 。

接下来，我们将 $\textit{heights}[i]$ 入栈，继续遍历下一个人。

遍历结束后，返回答案数组 $\textit{ans}$ 。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是数组 $\textit{heights}$ 的长度。

相似题目：

2282. 在一个网格中可以看到的人数

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def canSeePersonsCount(self, heights: List[int]) -> List[int]:
        n = len(heights)
        ans = [0] * n
        stk = []
        for i in range(n - 1, -1, -1):
            while stk and stk[-1] < heights[i]:
                ans[i] += 1
                stk.pop()
            if stk:
                ans[i] += 1
            stk.append(heights[i])
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n) because each person is pushed and popped at most once. Space complexity is O(n) for the stack storing intermediate heights during processing.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Consider edge cases where tallest person is at the end of the queue.
question_mark
Ask about naive O(n^2) approach versus stack optimization.
question_mark
Probe how stack state helps count visible people efficiently.

warning

常见陷阱

外企场景

error
Forgetting to count the first taller person after popping shorter ones.
error
Confusing index order when iterating from right to left.
error
Failing to maintain monotonic stack leading to incorrect visibility counts.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute visible people to the left using similar stack logic.
arrow_right_alt
Handle queues with non-unique heights using modified comparison rules.
arrow_right_alt
Extend to 2D grids to count visible people in multiple directions.

help

常见问题

外企场景

继续练习

#1996 游戏中弱角色的数量 #1856 子数组最小乘积的最大值 #1793 好子数组的最大分数