All problems

Number of Visible People in a Queue

Hard · monotonic-stack

People stand in a line, all facing right. heights[i] is the height of the person at position i. Heights may repeat.

Person i can see person j (with j > i) if every person standing strictly between them is shorter than both of them. Two people who stand next to each other can always see each other. People cannot see anyone behind them.

Return a list where entry i is the number of people that person i can see.

Examples

Example 1

Input: heights = [4, 2, 3, 1, 5]

Output: [3, 1, 2, 1, 0]

The first person (4) sees the 2, the 3 (the 2 between them is shorter than both) and the 5 (the people between are all shorter than 4), but not the 1, which the 3 hides. The person of height 2 sees only the 3 next to them.

Example 2

Input: heights = [5, 4, 3, 2, 1]

Output: [1, 1, 1, 1, 0]

Everyone is taller than the people further along, so each person sees only the neighbour in front of them, whose height blocks the rest.

Example 3

Input: heights = [3, 3, 3]

Output: [1, 1, 0]

The first 3 sees the second 3, but the second 3 is not shorter than the first, so it blocks the third.

Constraints