题目描述
思路：枚举+优化(单调栈)
先固定矩阵的高。
然后向左向右找到第一个比当前元素值小的元素，确定好左右边界。
对于元素2来说：
- 向左找到第一个比当前元素值小的元素：1的右边界
- 向右找到第一个比当前元素值小的元素：3的右边界
枚举每个元素的上边界，确定往左数最远到达哪个边界(即寻找左边第一个比它小的数)，往右数最远到达哪个边界(即寻找右边第一个比它小的数)
思路总结：
- 对于一个高度，如果能得到向左和向右的边界
- 那么就能对每个高度求一次面积
- 遍历所有高度，即可得出最大面积
- 使用单调栈，在出栈操作时得到前后边界并计算面积
☆方法一：
class Solution {
public int largestRectangleArea(int[] heights) {
int[] left = new int[heights.length];
Arrays.fill(left, -1);
Deque<Integer> stack = new ArrayDeque<>();
// 计算每根柱子左边第一个小于这根柱子的柱子
for (int i = heights.length - 1; i >= 0; i --) {
while (!stack.isEmpty() && heights[i] < heights[stack.peek()]) {
left[stack.peek()] = i;
stack.pop();
}
stack.push(i);
}
// 计算每根柱子左边第一个小于这根柱子的柱子
int[] right = new int[heights.length];
Arrays.fill(right, heights.length);
stack = new ArrayDeque<>();
for (int i = 0; i < heights.length; i ++) {
while (!stack.isEmpty() && heights[i] < heights[stack.peek()]) {
right[stack.peek()] = i;
stack.pop();
}
stack.push(i);
}
int res = 0;
for (int mid = 0; mid < heights.length; mid ++) {
int height = heights[mid];
res = Math.max(res, height * (right[mid] - left[mid] - 1));
}
return res;
}
}
- left数组：初始化为-1
- right数组：初始化为lengths.length
- 宽度：right[i] - left[i] - 1
- 高度：heights[i]
- 时间复杂度：O(n)
- 空间复杂度：O(n)
从右开始遍历：求得左边界
for (int i = heights.length - 1; i >= 0; i --) {
while (!stack.isEmpty() && heights[i] < heights[stack.peek()]) {
left[stack.peek()] = i;
stack.pop();
}
stack.push(i);
}
从左开始遍历：求得右边界
for (int i = 0; i < heights.length; i ++) {
while (!stack.isEmpty() && heights[i] < heights[stack.peek()]) {
right[stack.peek()] = i;
stack.pop();
}
stack.push(i);
}
方法二：
class Solution {
public int largestRectangleArea(int[] heights) {
int[] left = new int[heights.length];
Deque<Integer> stack = new ArrayDeque<>();
// 计算每根柱子左边第一个小于这根柱子的柱子
for (int i = 0; i < heights.length; i ++) {
while (!stack.isEmpty() && heights[i] <= heights[stack.peek()]) {
stack.pop();
}
left[i] = stack.isEmpty() ? -1 : stack.peek();
stack.push(i);
}
// 计算每根柱子左边第一个小于这根柱子的柱子
int[] right = new int[heights.length];
Arrays.fill(right, heights.length);
stack = new ArrayDeque<>();
for (int i = heights.length - 1; i >= 0; i --) {
while (!stack.isEmpty() && heights[i] <= heights[stack.peek()]) {
stack.pop();
}
right[i] = stack.isEmpty() ? heights.length : stack.peek();
stack.push(i);
}
int res = 0;
for (int mid = 0; mid < heights.length; mid ++) {
int height = heights[mid];
res = Math.max(res, height * (right[mid] - left[mid] - 1));
}
return res;
}
}
从左开始遍历：求得左边界
for (int i = 0; i < heights.length; i ++) {
while (!stack.isEmpty() && heights[i] <= heights[stack.peek()]) {
stack.pop();
}
left[i] = stack.isEmpty() ? -1 : stack.peek();
stack.push(i);
}
从右开始遍历：求得右边界
for (int i = heights.length - 1; i >= 0; i --) {
while (!stack.isEmpty() && heights[i] <= heights[stack.peek()]) {
stack.pop();
}
right[i] = stack.isEmpty() ? heights.length : stack.peek();
stack.push(i);
}
方法三：单调栈一次遍历
结合方法一和方法二，通过一次循环搞定。
需要保证两个for循环遍历的方向一致。