NeetCode #377LC-1944HardStack
← Back to All Problems#377 · #1944 · Number of Visible People in a Queue(队列中可以看到的人数)
📌 Problem Statement & Constraints
There are
n people in a queue, heights[i] is the height of the i-th person. A person can see the next person to the right who is taller, and everyone shorter in between. Return an array where answer[i] is the number of people person i can see to their right. Constraints: 1 <= n <= 10^5, 1 <= heights[i] <= 10^5.💡 Core Algorithmic Approaches
- Scan from right to left with a monotonically decreasing stack of indices.
- For each person, pop everyone shorter than them: each popped person is visible, and their own view is already accounted for.
- If the stack is still non-empty after popping, the new top is at least as tall and blocks everyone behind it -- but is itself visible, adding one.
- Push the current index. Each index is pushed and popped once, giving O(n).
💻 Benchmark Python3 Implementation
class Solution:
def canSeePersonsCount(self, heights: List[int]) -> List[int]:
n = len(heights)
res = [0] * n
st = [] # decreasing heights, indices
for i in range(n - 1, -1, -1):
cnt = 0
while st and heights[st[-1]] < heights[i]:
cnt += 1 # visible, and it does not block
st.pop()
if st:
cnt += 1 # the first taller-or-equal person
res[i] = cnt
st.append(i)
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each index is pushed once and popped at most once.
💾 Space Complexity
O(n) for the stack.
⚠️ Interview Pitfalls & Follow-ups
- Forgetting the
if st: cnt += 1: the person who finally blocks the view is still visible. - Using
<=in the pop condition: an equal-height person blocks the view, so only strictly shorter people are popped. - Scanning left to right: the visibility depends on the taller people to the right, so the scan must go backwards.
- Trying a nested loop: O(n^2) with n = 10^5.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.