Java Template
Use Stack or Deque in ascending or descending order
- time = O(n)
- space = O(n)
Leetcode 1944. Number of Visible People in a Queue
class Solution {
public int[] canSeePersonsCount(int[] heights) {
int[] res = new int[heights.length];
Stack<Integer> stack = new Stack<>();
for (int i = heights.length - 1; i >= 0; i--) {
int count = 0;
while (!stack.isEmpty() && heights[i] >= stack.peek()) {
stack.pop();
count++;
}
if (!stack.isEmpty()) {
count++;
}
stack.push(heights[i]);
res[i] = count;
}
return res;
}
}
Relevant questions
- https://leetcode.com/problems/number-of-visible-people-in-a-queue/
- https://leetcode.com/problems/next-greater-element-ii/
- https://leetcode.com/problems/largest-rectangle-in-histogram/
