LeetCode 84 柱状图中最大的矩形 - 单调栈解法
说明
下面保留了两种写法：
- 第一段是枚举区间的思路。
- 第二段是单调栈优化写法，核心是“在弹栈时结算面积”。
class Solution {
public int largestRectangleArea(int[] heights) {
int n = heights.length;
int ans = 0;
// 枚举 [i,j]
for (int i = 0; i < n; i++) {
int min = Integer.MAX_VALUE;
int area = 0;
for (int j = i; j < n; j++) {
if (heights[j] < min) {
min = heights[j];
area = (j - i + 1) * min;
} else {
area += min;
}
ans = Math.max(ans, area);
}
}
return ans;
}
public int largestRectangleArea1(int[] heights) {
int n = heights.length;
int ans = 0;
// 递增栈
Deque<Integer> deque = new LinkedList<>();
for(int i = 0;i<n;i++){
while (!deque.isEmpty()&&heights[i]<heights[deque.peek()]) {
int top = deque.pop();
// height[i]<height[top], 可以计算 高为 height[top] 的矩形
// 左边界是弹出后栈顶, 有边界是height[i]
int left = -1;
if (!deque.isEmpty()) {
left = deque.peek();
}
int area = (i-1-(left+1)+1)*heights[top];
ans = Math.max(ans, area);
}
deque.push(i);
}
// 可能栈中还有
while (!deque.isEmpty()) {
int top = deque.pop();
// 右侧找不到比 height[top]小的, 因此 right = n;
int right = n;
int left = -1;
if (!deque.isEmpty()) {
left = deque.peek();
}
int area = (right-1-(left+1)+1)*heights[top];
ans = Math.max(ans, area);
}
return ans;
}
}
单调栈
- 遇到相等高度时继续入栈。因为本题在弹栈时计算面积，要保证每个位置都能被结算一次。