单调栈
单调栈常用来解决 查找每个数左侧第一个比它小(大、小于等于、大于等于)的数的问题。
柱状图中最大的矩形(困难)
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。LeetCode84
思路：枚举所有柱形的上边界，作为整个矩形的上边界，然后去求左右边界。
1.找出左边离它最近的，比它小的柱形 left
2.找出右边离它最近的，比它小的柱形 right
参考代码
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
int largestRectangleArea(vector<int>& heights) {
int n = heights.size();
vector<int> left(n), right(n);
stack<int> stk;
// 从左向右遍历，维护一个单调递减的栈
for (int i = 0; i < n; i++) {
while (stk.size() && heights[stk.top()] >= heights[i]) stk.pop();
if (stk.empty())
left[i] = -1; // 注意这儿相当于负无穷
else
left[i] = stk.top();
stk.push(i);
}
while (stk.size()) stk.pop(); // 需要将栈弹空
// 向右向左遍历，维护一个单调递减的栈
for (int i = n - 1; i >= 0; i--) {
while (stk.size() && heights[stk.top()] >= heights[i]) stk.pop();
if (stk.empty())
right[i] = n;
else
right[i] = stk.top();
stk.push(i);
}
int res = 0;
// 遍历一次 更新答案
for (int i = 0; i < n; i++)
res = max(res, heights[i] * (right[i] - left[i] - 1));
return res;
}
接雨水(困难)
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。LeetCode42
思路：维护一个单调递减的栈
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int trap(vector<int>& height) {
int res = 0;
stack<int> stk;
for (int i = 0; i < height.size(); i++) {
int last = 0; // 记录之前的高度
// 维护一个单调递减栈
while (stk.size() && height[stk.top()] <= height[i]) {
int t = stk.top();
stk.pop();
// 当前层的雨水
res += (height[t] - last) * (i - t - 1);
last = height[t]; // 之前的高度更新为当前高度
}
// 右边墙低于左边墙的情况
if (stk.size()) res += (height[i] - last) * (i - stk.top() - 1);
stk.push(i);
}
return res;
}
每日温度(中等)
根据每日 气温 列表，请重新生成一个列表，对应位置的输出是需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。每日温度
参考代码
1
2
3
4
5
6
7
8
9
10
11
vector<int> dailyTemperatures(vector<int>& T) {
vector<int> res(T.size());
stack<int> stk;
for (int i = T.size() - 1; i >= 0; i--) {
// 维护一个单调递减栈
while (!stk.empty() && T[stk.top()] <= T[i]) stk.pop();
res[i] = stk.empty() ? 0 : stk.top() - i;
stk.push(i);
}
return res;
}
移掉k位数字(中等)
给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。移掉K位数字
参考代码
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
class Solution {
public:
/**
* 单调栈
* 利用栈存储当前迭代数字之前的数字，对于每一个数字，和栈顶元素比较，即该数字的左邻居
* 如果小于栈顶元素，则出栈。
* 从左向右依次扫描，如果前一个位置的数字比当前数字大，则把前一个数字删除，如果是递增的话，从最后面删除
* 时间复杂度：O(n)
* 空间复杂度：O(n)
*/
string removeKdigits(string num, int k) {
stack<char> stk;
for (auto c : num) {
while (k && stk.size() && stk.top() > c) { // 单调递增栈
stk.pop();
k--;
}
stk.push(c);
}
while(k > 0) stk.pop(), k--; // 如果原本就是递增的，则在末尾删除
string res;
while (stk.size()) {
res += stk.top();
stk.pop();
}
reverse(res.begin(), res.end());
int idx = 0;
while (res[idx] == '0') idx++;
res = res.substr(idx);
return res == "" ? "0" : res;
}
};
去除重复字母/不同字符的最小子序列(困难)
给你一个仅包含小写字母的字符串，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）。去除重复字母,不同字符的最小子序列
参考代码
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
class Solution {
public:
/**
* 单调栈
* 时间复杂度：O(n)
* 空间复杂度：O(n)
*/
string removeDuplicateLetters(string s) {
if (s.empty()) return s;
unordered_map<char, int> pos; // 用来存储每个字符最后出现的位置
unordered_set<char> hash; // 用来记录栈中字符
stack<int> stk; // 单调递增栈
int n = s.size();
for (int i = 0; i < n; i++) pos[s[i]] = i;
for (int i = 0; i < n; i++) {
auto c = s[i];
if (!hash.count(c)) { // 如果栈中不存在当前字符
// 维护单调递增栈，并保证在之后还有栈顶字母
while (stk.size() && stk.top() > c && pos[stk.top()] > i) {
hash.erase(stk.top());
stk.pop();
}
stk.push(c);
hash.insert(c);
}
}
string res;
while (stk.size()) {
res += stk.top();
stk.pop();
}
reverse(res.begin(), res.end());
return res;
}
};
单调队列
常用求解 滑动窗口中的最值
滑动窗口的最大值(困难)
给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。LeetCode239
思路：维护一个单调队列
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> res;
deque<int> q;
for (int i = 0; i < nums.size(); i++){
// 判断队头是否需要出队
if (q.size() && i -k + 1 > q.front()) q.pop_front();
// 维护一个单调队列
while (q.size() && nums[q.back()] < nums[i]) q.pop_back();
q.push_back(i);
// 判断是否需要添加进结果数组中
if (i >= k - 1) res.push_back(nums[q.front()]);
}
return res;
}
环形子数组的最大和(中等)
给定一个由整数数组 A 表示的环形数组 C，求 C 的非空子数组的最大可能和。LeetCode918
思路：将环形数组展开成两倍的普通数组，然后求前缀和，再维护一个单调递减的队列，转化为给定区间求最小的问题
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int maxSubarraySumCircular(vector<int>& A) {
int n = A.size();
// 将环形链表展成两倍的数组
for (int i = 0; i < n; i++) A.push_back(A[i]);
vector<int> sum(n * 2 + 1);
// 求前缀和
for (int i = 1; i <= 2 * n; i++) sum[i] = sum[i - 1] + A[i - 1];
int res = INT_MIN;
deque<int> q;
q.push_back(0); // 前缀和为0的情况
for (int i = 1; i <= 2 * n; i++) {
// i -n > q.front()) 如何理解？？
if (q.size() && i - n > q.front()) q.pop_front();
// 更新答案
if (q.size()) res = max(res, sum[i] - sum[q.front()]);
// 维护一个单调递减队列
while (q.size() && sum[q.back()] >= sum[i]) q.pop_back();
q.push_back(i);
}
return res;
}
