这道题是 LeetCode 第84题,liweiwei题解暴力解法、栈(单调栈、哨兵技巧)
题意
给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1。求在该柱状图中,能够勾勒出来的矩形的最大面积。
以上是柱状图的示例,其中每个柱子的宽度为 1,给定的高度为[2, 1, 5, 6, 2, 3]
。
图中阴影部分为所能勾勒出的最大矩形面积,其面积为 10
个单位。
思路
首先,要想找到第 i 个位置最大面积是什么?这个其实才是这个问题最关键的点。
是以 i 为中心,向左找第一个小于 heights[i]
的位置 left_i
;向右找第一个小于 heights[i]
的位置 right_i
,
即最大面积为 heights[i] * (right_i - left_i - 1)
,如下图所示:
所以,我们的问题就变成如何找到 right_i
和 left_i
?
1. 暴力解法
最简单的思路就是暴力解法(Brute Force),直接利用循环,当循环到 i 时,分别在 i 左右两边分别再接一次循环来寻找相应的值。
2. 动态规划
当我们找 i 左边第一个小于 hegihts[i]
如果 heights[i - 1] >= heights[i]
,其实就是和求 heights[i - 1]
左边第一个小于 heights[i - 1]
一样。以此类推,右边同理。
3. 单调栈
其实上面动态规划的解法使用空间换时间,同样的单调栈也是利用栈来记录信息从而达到时间换空间的目的。
那记录什么信息呢?记录高度是不是可以呢?其实是不够的,因为计算矩形还需要计算宽度,很容易知道宽度是由下标确定的,记录了下标其实对应的高度就可以直接从输入数组中的得出,因此,应该记录的是下标。
代码
1. 暴力解法
public class Solution {
public int largestRectangleArea(int[] heights) {
int len = heights.length;
int res = 0;
for (int i = 0; i < len; i++) {
int curHeight = heights[i];
// 找左边最后 1 个大于等于 heights[i] 的下标
int left = i;
while (left > 0 && heights[left - 1] >= curHeight) {
left--;
}
// 找右边最后 1 个大于等于 heights[i] 的下标
int right = i;
while (right < len - 1 && heights[right + 1] >= curHeight) {
right++;
}
int width = right - left + 1;
res = Math.max(res, width * curHeight);
}
return res;
}
}
2. 动态规划
class Solution {
public int largestRectangleArea(int[] heights) {
if (heights == null || heights.length == 0) {
return 0;
}
int n = heights.length;
int[] left_i = new int[n];
int[] right_i = new int[n];
left_i[0] = -1;
right_i[n - 1] = n;
int res = 0;
for (int i = 1; i < n; i++) {
int temp = i - 1;
while (temp >= 0 && heights[temp] >= heights[i]) {
temp = left_i[temp];
}
left_i[i] = temp;
}
for (int i = n - 2; i >= 0; i--) {
int temp = i + 1;
while (temp < n && heights[temp] >= heighes[i]) {
temp = right_i[temp];
}
right_i[i] = temp;
}
for (int i = 0; i < n; i--) {
res = Math.max(res, (right_i[i] - left_i[i] - 1) * heights[i]);
}
}
}
3. 单调栈
class Solution {
public int largestRectangleArea(int[] heights) {
int len = heights.length, res = 0;
Deque<Integer> stack = new ArrayDeque<>(len);
for (int i = 0; i < len; i++) {
// 这个 while 很关键,因为可能不止一个柱形的最大宽度可以被计算出来
while (!stack.isEmpty() && heights[i] < heights[stack.peekLast()]) {
int curHeight = heights[stack.pollLast()];
while (!stack.isEmpty() && heights[stack.peekLast()] == curHeight) {
stack.pollLast();
}
int curWidth;
if (stack.isEmpty()) {
curWidth = i;
} else {
curWidth = i - stack.peekLast() - 1;
}
res = Math.max(res, curHeight * curWidth);
}
stack.addLast(i);
}
while (!stack.isEmpty()) {
int curHeight = heights[stack.pollLast()];
while (!stack.isEmpty() && heights[stack.peekLast()] == curHeight) {
stack.pollLast();
}
int curWidth;
if (stack.isEmpty()) {
curWidth = len;
} else {
curWidth = len - stack.peekLast() - 1;
}
res = Math.max(res, curHeight * curWidth);
}
return res;
}
}
以上代码需要考虑两种特殊的情况:
- 弹栈的时候,栈为空;
- 遍历完成以后,栈中还有元素;
为此我们可以在输入数组的两端加上两个高度为 0 (或者是 0.5,只要比 1 严格小都行)的柱形,可以回避上面这两种分类讨论。
这两个站在两边的柱形有一个很形象的名词,叫做哨兵(Sentinel)。
有了这两个柱形:
- 左边的柱形(第一个柱形)由于它一定比输入数组里任何一个元素小,它肯定不会出栈,因此栈一定不为空;
- 右边的柱形(最后的柱形)也正是因为它一定比输入数组里任何一个元素小,它会让所有输入数组里的元素出栈(第一个哨兵元素除外)。
这里栈对应到高度,呈单调增加不减的形态,因此称为单调栈(Monotone Stack)。它是暴力解法的优化,计算每个柱形的高度对应的最大矩形的顺序由出栈顺序决定。
下面是加入了哨兵的写法:
class Solution {
public int largestRectangleArea(int[] heights) {
int len = heights.length, res = 0;
Deque<Integer> stack = new ArrayDeque<>();
int[] new_heights = new int[len + 2];
System.arraycopy(heights, 0, new_heights, 1, len);
for (int i = 0; i < new_heights.length; i++) {
while (!stack.isEmpty() && new_heights[stack.peek()] > new_heights[i]) {
int cur = stack.pop();
res = Math.max(res, (i - stack.peek() - 1) * new_heights[cur]);
}
stack.push(i);
}
return res;
}
}