单调栈

单调栈理解起来很容易,但是实际运用却没那么简单。一句话解释单调栈,就是一个栈,里面的元素的大小按照他们所在栈内的位置,满足一定的单调性。

下面结合题目,在实战中学会使用单调栈解决问题。

Google面试题

(google面试)题目: 给一个数组,返回一个大小相同的数组。返回的数组的第i个位置的值应当是,对于原数组中的第i个元素,至少往右走多少步,才能遇到一个比自己大的元素(如果之后没有比自己大的元素,或者已经是最后一个元素,则在返回数组的对应位置放上-1)。

简单的例子:

input: 5,3,1,2,4

return: -1 3 1 1 -1

解决方案:递减栈

implementation:

1
2
3
4
5
6
7
8
9
10
11
12
vector<int> nextExceed(vector<int> &input) {
vector<int> result (input.size(), -1);
stack<int> monoStack;
for(int i = 0; i < input.size(); ++i) {
while(!monoStack.empty() && input[monoStack.top()] < input[i]) {
result[monoStack.top()] = i - monoStack.top();
monoStack.pop();
}
monoStack.push(i);
}
return result;
}

LeetCode-42

题目: LeetCode-42. Trapping Rain Water

解决方案:递减栈

implementation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
int trap(vector<int>& height) {
vector<int> st(height.size());
int head = -1;
int res = 0;
for (int i = 0; i < height.size(); i++) {
while (head >= 0 && height[st[head]] <= height[i]) {
if (st[head] + 1 != i) {
res += (height[st[head]] - height[st[head + 1]]) * (i - st[head] - 1);
}
head--;
}
if (head >= 0) res += (height[i] - height[st[head + 1]]) * (i - st[head] - 1);
st[++head] = i;
}
return res;
}
};

LeetCode-84

题目:LeetCode-84. Largest Rectangle in Histogram

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given heights = [2,1,5,6,2,3],
return 10.

解决方案:递增栈

implementation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int largestRectangleArea(vector<int> &height) {
int ret = 0;
height.push_back(0);
stack<int> index;
for(int i = 0; i < height.size(); i++) {
while(index.size() > 0 && height[index.top()] > height[i]) {
// 计算以index.top()为轴的矩形大小,左右两边是已从栈中弹出的比index.top()高的小矩形
int h = height[index.top()];
index.pop();
int idx = index.empty() ? -1 : index.top();
ret = max(ret, (i - idx - 1) * h);
}
index.push(i);
}
return ret;
}

LeetCode-85

题目: LeetCode-85. Maximal Rectangle

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.

Example:

1
2
3
4
5
6
7
8
Input:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
Output: 6

implementation:

方法一: 单调递增栈(20ms)
实质上与LeetCode-84求最大矩形面积等价,通过迭代行来更新高度数组

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
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
if (matrix.size() == 0) return 0;
int m = matrix.size(), n = matrix[0].size();
vector<int> height(n, 0);
int ret = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == '0') height[j] = 0;
else height[j]++;
}
ret = max(ret, largestRectangleArea(height));
}
return ret;
}
private:
int largestRectangleArea(vector<int> &height) {
int ret = 0;
height.push_back(0);
stack<int> index;
for(int i = 0; i < height.size(); i++) {
while(index.size() > 0 && height[index.top()] > height[i]) {
int h = height[index.top()];
index.pop();
int idx = index.empty() ? -1 : index.top();
ret = max(ret, (i - idx - 1) * h);
}
index.push(i);
}
height.pop_back();
return ret;
}
};

方法二:动态规划dp(16ms)
lefts[j]和rights[j]分别存储以height[j]为高度的矩阵的左边界和右边界

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
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
if (matrix.size() == 0) return 0;
int m = matrix.size(), n = matrix[0].size();
vector<int> heights(n, 0), lefts(n, 0), rights(n, n);
int ret = 0;
for (int i = 0; i < m; i++) {
int cur_left = 0, cur_right = n;
for (int j = 0; j < n; j++) {
if (matrix[i][j] == '0') heights[j] = 0;
else heights[j]++;
if (heights[j] > 0) {
lefts[j] = max(cur_left, lefts[j]);
} else {
lefts[j] = 0;
cur_left = j + 1;
}
}
for (int j = n - 1; j >= 0; j--) {
if (heights[j] > 0) {
rights[j] = min(cur_right, rights[j]);
} else {
rights[j] = n;
cur_right = j;
}
}
for (int j = 0; j < n; j++) {
ret = max(ret, (rights[j] - lefts[j]) * heights[j]);
}
}
return ret;
}
};

方法三:暴力枚举(60ms)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
if (matrix.size() == 0) return 0;
int m = matrix.size(), n = matrix[0].size();
vector<int> heights(n, 0);
int ret = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == '0'){
heights[j] = 0;
continue;
} else heights[j]++;
int min_height = heights[j];
for (int k = j; k >= 0; k--) {
min_height = min(heights[k], min_height);
ret = max(ret, (j - k + 1) * min_height);
}
}
}
return ret;
}
};
---------------- The End ----------------

作者: brooksj
联系邮箱: jaypark@smail.nju.edu.cn
本文地址: https://brooksj.com/2019/05/28/%E5%8D%95%E8%B0%83%E6%A0%88/
本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
转载请注明出处, 谢谢!