We need to maintain a monotonically increasing stack, so that we can easily calculate the largest rectangle area whenever we meet a new bar i. Each time we meet a new bar i, if the height of the new bar heights[i] is larger than the top element of the stack heights[stack.peekLast()], we just push it into the stack and finish this round. Otherwise, we pop out the top element of the stack height = heights[stack.pollLast()], and we calculate the area of the rectangle centered at the popped element. So the height is the popped element's height, and the left boundary would be stack.peekLast() + 1, the right boundary would be i - 1. Thus, the area center at the popped element would be height * (i - 1 - stack.peekLast() - 1 + 1), which would be the largest rectangle centered at the popped element.
public int largestRectangleArea(int[] heights) {
Deque<Integer> stack = new LinkedList<>();
int max = 0;
for (int i = 0; i <= heights.length; i++) {
// To pop out all the elements in the stack at last, so we explicitly add a bar of height 0.
int cur = i == heights.length ? 0 : heights[i];
while (!stack.isEmpty() && heights[stack.peekLast()] >= cur) {
int height = heights[stack.pollLast()];
// Dertermine the left boundary of the largest rectangle with height heights[i]
int left = stack.isEmpty() ? 0 : stack.peekLast() + 1;
// Dertermine the right boundary of the largest rectangle with height of the poped element
max = Math.max(max, height * (i - 1 - left + 1));
}
stack.offerLast(i);
}
return max;
}
这里也是维护一个单调栈（max的话，递减栈；min的话，递增栈）
public static int[] compute(int[] array, int window, boolean maximize) {
int[] result = new int[array.length - window + 1];
Deque<Integer> deque = new ArrayDeque<>();
for (int i = 0; i < array.length; i++) { // Range end index (inclusive)
int val = array[i];
while (!deque.isEmpty() && (!maximize && val < deque.getLast() || maximize && val > deque.getLast()))
deque.removeLast();
deque.addLast(val);
int j = i + 1 - window; // Range start index, does not overflow
if (j >= 0) {
result[j] = deque.getFirst();
if (array[j] == result[j])
deque.removeFirst();
}
}
return result;
}
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
Deque<Integer> destack = new LinkedList<>();
if (nums == null || nums.length == 0) return nums;
int[] res = new int[nums.length - k + 1];
for (int i = 0; i < nums.length; i++) {
int cur = nums[i];
while (!destack.isEmpty() && nums[destack.peekLast()] < cur) {
destack.pollLast();
}
destack.offerLast(i);
if (i >= k - 1) {
// [i - k + 1 , i]
if (destack.peekFirst() < i - k + 1) {
destack.pollFirst();
}
res[i - k + 1] = nums[destack.peekFirst()];
}
}
return res;
}
}
