题目
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1:
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10示例 2：
输入： heights = [2,4]
输出： 4提示：
1 <= heights.length <=10^50 <= heights[i] <= 10^4
解题
方法一：暴力(超时)
思路
遍历 heights 中的每根柱子，以当前遍历到的柱子高度(height)为矩形高度，向左向右分别找到第一个小于当前高度的柱子，以其之间的距离为宽度计算出矩形面积，最后返回其中算出的最大面积。
代码
class Solution {
public int largestRectangleArea(int[] heights) {
int len = heights.length;
int ans = 0;
for (int i = 0; i < len; i++) {
int height = heights[i];
int left = i - 1, right = i + 1;
for (; left >= 0 && heights[left] >= height; left--) { }
for (; right < len && heights[right] >= height; right++) { }
int width = right - left - 1;
ans = Math.max(ans, width * height);
}
return ans;
}
}方法二：单调栈
思路
维护一个单调递增栈(monoStack)，存储索引，遍历高度数组：
- 如果栈不为空，且当前遍历到柱子的高度(
heightArr[i])小于栈顶元素对应的高度：- 就说明栈顶元素表示的柱子第一次在右边遇到了比自己矮的柱子，又因为是单调递减栈，所以栈顶元素表示的柱子在其左边遇到的第一个比自己矮的柱子就是在它下面的栈中元素。
- 把栈顶元素出栈，以其高度为矩形高度(
height)，再取当前的栈顶元素，以其到当前遍历到的柱子中间的距离(i-monoStack.peek()-1)为宽度，计算矩形的面积，并更新最大的矩形面积。 - 循环，直到当前遍历到柱子的高度大于等于栈顶元素对应的高度。
- 否则，直接将当前索引入栈。
其他解释：
单调栈分为单调递增栈和单调递减栈
- 单调递增栈即栈内元素保持单调递增的栈
- 同理单调递减栈即栈内元素保持单调递减的栈
操作规则（下面都以单调递增栈为例）
- 如果新的元素比栈顶元素大，就入栈
- 如果新的元素较小，那就一直把栈内元素弹出来，直到栈顶比新元素小
加入这样一个规则之后，会有什么效果？
- 栈内的元素是递增的
- 当元素出栈时，说明这个新元素是出栈元素向后找第一个比其小的元素
- 当元素出栈后，说明新栈顶元素是出栈元素向前找第一个比其小的元素
引入哨兵数组简化代码：
- 在
heights左右两侧各增加一个元素 0 - 左边的作用是：将开头的元素顺利入栈
- 右边的作用是：将最后的元素出栈计算面积
代码
class Solution {
public int largestRectangleArea(int[] heights) {
// 引入哨兵
// 哨兵的作用是 将开头的元素顺利入栈 以及 将最后的元素出栈计算面积
// len为引入哨兵后的数组长度
int len = heights.length + 2;
int[] heightArr = new int[len];
System.arraycopy(heights, 0, heightArr, 1, len - 2);
// 单调递增栈: 存储每个柱子的索引,使得这些索引对应的柱子高度单调递增
Deque<Integer> monoStack = new LinkedList<>();
int ans = 0; // 最大矩形面积
for (int i = 0; i < len; i++) {
// 栈不为空且 当前柱子高度<栈顶索引对应的柱子高度
// 说明栈顶元素的右边界已经确定, 就是索引为i的柱子(不含)
while (!monoStack.isEmpty() && heightArr[i] < heightArr[monoStack.peek()]) {
// 此时将栈顶元素出栈, 其对应的柱子高度就是矩形的高度
int height = heightArr[monoStack.pop()];
// 栈顶矩形左边界为栈顶元素下面的索引(首个小于栈顶)
// 矩形宽度 = 右边界索引-左边界索引-1
int width = i - monoStack.peek() - 1;
// 维护矩形面积最大值
ans = Math.max(ans, height * width);
}
// 每当弹出一个索引就计算一个矩形面积
// 直到当前元素>=栈顶元素(或者栈为空)时, 栈顶柱子的右边界不确定
// 因此当前元素索引入栈即可
monoStack.push(i);
}
return ans;
}
}
评论区