单调栈（矩形面积/贡献法/最小字典序）
如果当前元素比栈顶小，直接入栈；否则，把所有小于等于它的元素弹出，再将其放入。因此，栈中的元素一定是有序的，称之为单调栈。
从右向左
如果当前元素比栈顶小，直接入栈，并且当前元素的下一个更高温度就是1；否则，把所有小于等于它的元素弹出，再将其放入，当前元素的下一个更高温度就是栈顶元素。即，找到第一个大于当前元素的栈中元素，其值应该是栈顶元素下标-当前元素下标。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = temperatures.size();
vector<int> ans(n);
stack<int> stk;
for(int i = n-1; i >= 0; i--){
while(!stk.empty() && temperatures[i] >= temperatures[stk.top()]){
stk.pop();
}
if(!stk.empty()){
ans[i] = stk.top() - i;
}
stk.push(i);
}
return ans;
}
};
|
- 时间复杂度：O(n)，每个元素最多入栈和出栈一次。
- 空间复杂度：O(n)，返回值不计入，仅考虑栈的最大空间消耗。
从左向右
从左向右遍历元素，如果当前元素比栈顶小，直接入栈，等待出现更大元素；否则，把所有小于等于它的元素弹出，并且可以更新每一个弹出的元素的结果，即i - stk.top()，再将当前元素放入。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = temperatures.size();
vector<int> ans(n);
stack<int> stk;
for(int i = 0; i < n; i++){
while(!stk.empty() && temperatures[i] > temperatures[stk.top()]){
ans[stk.top()] = i - stk.top();
stk.pop();
}
stk.push(i);
}
return ans;
}
};
|
单调栈
对于接雨水问题，也可以用单调栈的方法。从左往右遍历，如果当前元素比栈顶小，直接入栈，因为当前无法接雨水，直到当前元素比栈顶大，当前坑可以接的水为：取栈顶的下一个元素作为left，当前元素为right，宽度就是right - left - 1，高度为左右高度的较小值-栈顶柱子的高度，即min(height[left], height[i]) - height[stk.top()]。
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
| class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
stack<int> stk;
int ans = 0;
for(int i = 0; i < n; i++){
while(!stk.empty() && height[i] > height[stk.top()]){
int bottom = stk.top();
stk.pop();
if(stk.empty()){
break;
}
int left = stk.top();
int dh = min(height[left], height[i]) - height[bottom];
ans += dh * (i - left - 1);
}
stk.push(i);
}
return ans;
}
};
|
单调栈
从左向右遍历，当前元素大于栈顶，就入栈，否则不断出栈，并更新当前出栈元素的折扣价，即prices[stk.top()] - prices[i]。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
vector<int> finalPrices(vector<int>& prices) {
int n = prices.size();
vector<int> ans = prices;
stack<int> stk;
for(int i = 0; i < n; i++){
while(!stk.empty() && prices[i] <= prices[stk.top()]){
int j = stk.top();
stk.pop();
ans[j] = prices[j] - prices[i];
}
stk.push(i);
}
return ans;
}
};
|
不得不说灵神讲得太好了，我居然也能看过视频之后自己把题目做出来了╰(°▽°)╯ 后面再多做几道题练习一下~
单调栈
- 先将nums2所有数字存到哈希表中，这样可以通过O(1)的时间找到其索引。
- 用单调栈的方法处理nums2，找其下一个更大元素的下标，存到数组里。
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
| class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
int n1 = nums1.size();
int n2 = nums2.size();
vector<int> mono(n2, -1);
stack<int> stk;
for(int i = 0; i < n2; i++){
while(!stk.empty() && nums2[i] > nums2[stk.top()]){
int j = stk.top();
stk.pop();
mono[j] = i;
}
stk.push(i);
}
unordered_map<int, int> hash;
for(int i = 0; i < n2; i++){
hash[nums2[i]] = i;
}
vector<int> ans(n1);
for(int i = 0; i < n1; i++){
int index = hash[nums1[i]];
ans[i] = mono[index] == -1 ? -1 : nums2[mono[index]];
}
return ans;
}
};
|
- 时间复杂度：O(n1 + n2)
- 空间复杂度：O(n2)
上面的解法是自己写出来的，力扣官方题解省略了哈希表存储nums2的部分，节省了空间。灵神的做法是省去了存储nums2中其他元素的方法，只存nums1中存在的元素。
单调栈
和上一题的区别是，这道题的数组可以循环，也就是说，先找到数组元素下标后边的第一个比它大的元素，如果没有，可以从下标0开始找。可以把 nums 复制一份，拼在 nums 右边，这样就把环形数组变成一般数组了。例如 [1,2,1] 变成 [1,2,1,1,2,1]。无需真的把数组复制一份，而是用下标模 n 的方式取到对应的元素值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
int n = nums.size();
vector<int> ans(n, -1);
stack<int> stk;
for(int i = 0; i < 2 * n; i++){
int x = nums[i % n];
while(!stk.empty() && x > nums[stk.top()]){
int j = stk.top();
stk.pop();
ans[j] = x;
}
if(i < n){
stk.push(i);
}
}
return ans;
}
};
|
单调栈
可以先遍历一遍链表得到其长度，确定答案数组的大小。然后将每个节点保存在栈中。
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
|
class Solution {
public:
vector<int> nextLargerNodes(ListNode* head) {
unordered_map<ListNode*, int> hash;
int n = 0;
ListNode* node = head;
while(node){
hash[node] = n++;
node = node->next;
}
vector<int> ans(n);
stack<ListNode*> stk;
node = head;
int index = 0;
while(node){
while(!stk.empty() && node->val > stk.top()->val){
int i = hash[stk.top()];
stk.pop();
ans[i] = node->val;
}
stk.push(node);
node = node->next;
}
return ans;
}
};
|
上面是自己写的解法，官方题解省略了第一次遍历得到长度以及哈希表，在栈中存储的是节点的值和它的索引。
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:
vector<int> nextLargerNodes(ListNode* head) {
vector<int> ans;
stack<pair<int, int>> stk;
ListNode* node = head;
int index = 0;
while(node){
ans.push_back(0);
while(!stk.empty() && stk.top().first < node->val){
ans[stk.top().second] = node->val;
stk.pop();
}
stk.emplace(node->val, index);
index++;
node = node->next;
}
return ans;
}
};
|
思路是一样的，但是节省了空间。
总结
单调栈的题目大概做了6道，基本的思路已经理解并且能够自己做出来不太复杂的题目。先到这里，以后再刷。