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 ith
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 ith person can see the jth person if i < j and min(heights[i], heights[j]) > max(heights[i+1], heights[i+2], ..., heights[j-1]).
Return an arrayanswerof lengthnwhereanswer[i]_is thenumber of people the _ithperson cansee to their right in the queue.

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.
To count how many people each person can see to their right, process the queue from right to left using a stack. The stack keeps track of people who are visible and not blocked by a taller person. Each time a person is taller than the stack top, they can see the person and all people the stack top could see.
classSolution {
publicint[]canSeePersonsCount(int[] heights) {
int n = heights.length;
int[] ans =newint[n];
Deque<Integer> st =new ArrayDeque<>();
for (int i = n-1; i >= 0; i--) {
int cnt = 0;
while (!st.isEmpty() && heights[i]> heights[st.peek()]) {
cnt++;
st.pop();
}
if (!st.isEmpty()) cnt++;
ans[i]= cnt;
st.push(i);
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
classSolution {
funcanSeePersonsCount(heights: IntArray): IntArray {
val n = heights.size
val ans = IntArray(n)
val st = ArrayDeque<Int>()
for (i in n-1 downTo 0) {
var cnt = 0while (st.isNotEmpty() && heights[i] > heights[st.last()]) {
cnt++ st.removeLast()
}
if (st.isNotEmpty()) cnt++ ans[i] = cnt
st.addLast(i)
}
return ans
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
classSolution:
defcanSeePersonsCount(self, heights: list[int]) -> list[int]:
n = len(heights)
ans = [0]*n
st = []
for i in range(n-1, -1, -1):
cnt =0while st and heights[i] > heights[st[-1]]:
cnt +=1 st.pop()
if st:
cnt +=1 ans[i] = cnt
st.append(i)
return ans