Formatted question description: https://leetcode.ca/all/1944.html

# 1944. Number of Visible People in a Queue

## Level

Hard

## Description

There are `n`

people standing in a queue, and they numbered from `0`

to `n - 1`

in **left to right** order. You are given an array `heights`

of **distinct** integers where `heights[i]`

represents the height of the `i-th`

person.

A person can **see** another person to their right in the queue if everybody in between is **shorter** than both of them. More formally, the `i-th`

person can see the `j-th`

person if `i < j`

and `min(heights[i], heights[j]) > max(heights[i+1], heights[i+2], ..., heights[j-1])`

.

Return *an array answer of length n where answer[i] is the *.

**number of people**the i-th person can

**see**to their right in the queue

**Example 1:**

**Input:** heights = [10,6,8,5,11,9]

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

**Explanation:**

Person 0 can see person 1, 2, and 4.

Person 1 can see person 2.

Person 2 can see person 3 and 4.

Person 3 can see person 4.

Person 4 can see person 5.

Person 5 can see no one since nobody is to the right of them.

**Example 2:**

**Input:** heights = [5,1,2,3,10]

**Output:** [4,1,1,1,0]

**Constraints:**

`n == heights.length`

`1 <= n <= 10^5`

`1 <= heights[i] <= 10^5`

- All the values of
`heights`

are**unique**.

## Solution

Use monotonic stack. Loop over `heights`

backward. For each height `heights[i]`

, count the number of people that are already in the stack and have heights less than the current height, and pop the elements from the stack until the stack becomes empty or the top element of the stack is strictly greater than the current height, and push `heights[i]`

into the stack. The value of `answer[i]`

is the number of popped elements before pushing `heights[i]`

, and if the stack is not empty when stopping popping elements, add 1 to `answer[i]`

. Finally, return `answer`

.

```
class Solution {
public int[] canSeePersonsCount(int[] heights) {
int length = heights.length;
int[] counts = new int[length];
Deque<Integer> stack = new LinkedList<Integer>();
for (int i = length - 1; i >= 0; i--) {
int height = heights[i];
while (!stack.isEmpty()) {
int prevHeight = stack.peek();
counts[i]++;
if (prevHeight <= height)
stack.pop();
else
break;
}
stack.push(height);
}
return counts;
}
}
```