单调栈,思考起来比较费劲。
给定非负整数数组 heights ,数组中的数字用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
求在该柱状图中,能够勾勒出来的矩形的最大面积。
链接:https://leetcode.cn/problems/0ynMMM
还是使用单调栈。你会发现,这几道题的核心,都是利用一个单调栈,之后在遍历数组时,让当前元素和栈顶元素做比较,一直保证栈顶元素是最大(或最小)。
解答这一道题的几个核心点如下:
public int largestRectangleArea(int[] heights) {
Deque<Integer> stack = new ArrayDeque<>();
// 方便处理边界问题
stack.push(-1);
int result = 0;
for (int i = 0; i < heights.length; i++) {
int current = heights[i];
while (stack.peek() != -1 && heights[stack.peek()] > current) {
// 获取栈顶元素下标的同时移除了栈顶元素
int height = heights[stack.pop()];
int with = i - stack.peek() - 1;
result = Math.max(result, height * with);
}
stack.push(i);
}
// 处理栈中剩余的边界。此时右边界必然是数组的最右端
while (stack.peek()!=-1) {
result = Math.max(result, heights[stack.pop()] * (heights.length - stack.peek() - 1));
}
return result;
}
P.S.这个题解的动画很棒:https://leetcode.cn/problems/0ynMMM/solution/hua-luo-yue-que-wo-zhen-de-zhen-de-nu-li-ohjt/