分析图例可以发现,第 0个人可以看到的三个人的身高是严格递增的。如果满足 i<j,此时下标为 jjj 且靠后的人比下标为 i且靠前的人矮,那么下标为 j的人无法被下标 i之前的人看到。根据这个规律,我们可以想到利用单调栈来解决这个问题。从队伍末尾开始,维护一个单调栈,从栈底到栈顶,身高严格递减。
class Solution {
public int[] canSeePersonsCount(int[] heights) {
int n = heights.length;
Deque<Integer> stack = new ArrayDeque<Integer>();
int[] res = new int[n];
for(int i = n - 1; i >= 0; i--) {
int h = heights[i];
while(!stack.isEmpty() && stack.peek() < h) {
stack.pop();
res[i]++;
}
if(!stack.isEmpty()) {
res[i]++;
}
stack.push(h);
}
return res;
}
}