84 柱状图中最大的矩形
题目链接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
思考
我们可以反过来考虑针对于每一个元素，都可以求出以它为高的最大矩形面积。
那么这样一个矩形，它的底应该是多少呢？
自然而然，我们可以发现：这一个矩形的左侧就是左边比它小的元素的位置，右侧自然也是比它小的元素的位置。
以下图的元素5为例，它的最左侧就应该是比它小的元素1的右边，它的最右侧就应该是比它小的元素2的左边。
因此，问题就转化成了：针对于每一个元素，我们都需要求出左边比它小的元素的位置以及右边比它小的元素的位置。
单调栈
那么在从左往右遍历一遍的过程中，如何找出比它小的元素呢？
我们自然而然的想到了单调递增栈（严格单调递增）：每当一个元素到达时候，不断出栈直到栈为空或者栈顶元素小于该元素，那么这个元素就一定是比它小的最近的元素。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| function largestRectangleArea(heights: number[]): number {
let n = heights.length;
let left = new Array(n).fill(-1);
let right = new Array(n).fill(n);
let s = new Array();
for (let i = 0; i < n; ++i) {
while (s.length != 0 && heights[s[s.length - 1]] >= heights[i]) {
s.pop();
}
if (s.length != 0) {
left[i] = s[s.length - 1];
}
s.push(i);
}
s.splice(0, s.length);
for (let i = n - 1; i >= 0; --i) {
while (s.length != 0 && heights[s[s.length - 1]] >= heights[i]) {
s.pop();
}
if (s.length != 0) {
right[i] = s[s.length - 1];
}
s.push(i);
}
let maxRes = 0;
for (let i = 0; i < n; ++i) {
maxRes = Math.max(maxRes, (right[i] - left[i] - 1) * heights[i]);
}
return maxRes;
};
|
42 接雨水
题目链接：https://leetcode-cn.com/problems/trapping-rain-water/
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
思考
我们可以考虑计算每一根柱子所能接的雨水的高度。
这个高度应该是：左右两侧柱子的高度。其中这根柱子满足，它是这根柱子左边（或右边）比它高的那一根柱子所能接到雨水的高度。
注意：不是左边（或）右边比它高的柱子的高度，因为可能还有更高的柱子。实际上应该是接到雨水的高度，因为比它高的雨水能借到的柱子，它自己也一定能接到。
这样问题实际上就转化成了，寻找左边（或右边）最近的比它大的元素。
自然而然，我们应该使用单调递减栈（严格单调递减）：每遍历到一个元素的时候，不断出栈直到栈空或者栈顶元素大于该元素。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| function trap(height: number[]): number {
let n = height.length;
let left = new Array(n);
let right = new Array(n);
let s = [];
for (let i = 0; i < n; ++i) {
while (s.length != 0 && height[s[s.length - 1]] <= height[i]) {
s.pop();
}
if (s.length == 0) {
left[i] = height[i];
}
else {
left[i] = left[s[s.length - 1]];
}
s.push(i);
}
s.splice(0, s.length);
for (let i = n - 1; i >= 0; --i) {
while (s.length != 0 && height[s[s.length - 1]] <= height[i]) {
s.pop();
}
if (s.length == 0) {
right[i] = height[i];
}
else {
right[i] = right[s[s.length - 1]];
}
s.push(i);
}
let ans = 0;
for (let i = 0; i < n; ++i) {
ans += Math.min(left[i], right[i]) - height[i];
}
return ans;
};
|
