剑指 offer ii 039. 直方图最大矩形面积-爱代码爱编程
https://leetcode.cn/problems/0ynMMM/
题目要求
给定非负整数数组 heights ,数组中的数字用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
求在该柱状图中,能够勾勒出来的矩形的最大面积。
方法:双指针
- 用两个双指针数组来记录每个柱子左右两边的第一个小于的柱子的坐标
public int largestRectangleArea(int[] heights) {
int n = heights.length;
int[] minLeftIndex = new int[n];
int[] minRightIndex = new int[n];
minLeftIndex[0] = -1;// 注意这里初始化,防止下面while死循环
for (int i = 1; i < n; i++) {
int t = i - 1;
while (t >= 0 && heights[t] >= heights[i]) {
t = minLeftIndex[t];
}
minLeftIndex[i] = t;
}
minRightIndex[n - 1] = n;// 注意这里初始化,防止下面while死循环
for (int i = n - 2; i >= 0; i--) {
int t = i + 1;
while (t < n && heights[t] >= heights[i]) {
t = minRightIndex[t];
}
minRightIndex[i] = t;
}
int res = 0;
for (int i = 0; i < n; i++) {
int sum = heights[i] * (minRightIndex[i] - minLeftIndex[i] - 1);
res = Math.max(res, sum);
}
return res;
}
方法:单调栈
- 实际上也是借助单调栈来找出左右的边界,然后遍历每个柱子的左右边界进行比较
public int largestRectangleArea(int[] heights) {
int n = heights.length;
int[] left = new int[n];// 记录左边界
int[] right = new int[n];// 记录右边界
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < n; ++i) {
while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
stack.pop();
}
left[i] = (stack.isEmpty() ? -1 : stack.peek());
stack.push(i);
}
stack.clear();
for (int i = n - 1; i >= 0; --i) {
while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
stack.pop();
}
right[i] = (stack.isEmpty() ? n : stack.peek());
stack.push(i);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
}
return ans;
}