Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.
Example 1:
**Input:** heights = [2,1,5,6,2,3]
**Output:** 10
**Explanation:** The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.
Example 2:
**Input:** heights = [2,4]
**Output:** 4
Constraints:
1 <= heights.length <= 105
0 <= heights[i] <= 104
ac1: stack
stack & array push -1 at first, like #32 push 0 at last, like this one #84
class Solution {
public int largestRectangleArea(int[] heights) {
// edge cases
if (heights.length == 0) return 0;
int max = 0;
// stack iterate
Stack<Integer> stack = new Stack<Integer>();
stack.push(-1);
for (int i = 0; i <= heights.length; i++) {
int currh = i == heights.length ? 0 : heights[i];
while (stack.peek() != -1 && currh < heights[stack.peek()]) {
int h = heights[stack.pop()];
int w = i - stack.peek() - 1;
max = Math.max(max, h * w);
}
stack.push(i);
}
return max;
}
}
/*
stack
push -1 at first, like #32
push 0 at last, like this one #84
if stack.isEmpty() -> stack.peek() != -1 || heights[i] >= height[stack.peek()], push
while height[i] < height[stack.peek()], h = height[stack.pop()], w = i - stack.peek() - 1
*/
This is more intuitive without pushing -1 or 0:
class Solution {
public int largestRectangleArea(int[] heights) {
// edge cases
if (heights.length == 0) return 0;
int len = heights.length;
int max = 0;
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < heights.length; i++) {
while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
int h = heights[stack.pop()];
int w = stack.isEmpty() ? i : i - stack.peek() - 1;
max = Math.max(max, h * w);
}
stack.push(i);
}
while (!stack.isEmpty()) {
int h = heights[stack.pop()];
int w = stack.isEmpty() ? len : len - stack.peek() - 1;
max = Math.max(max, h * w);
}
return max;
}
}
