单调栈总结

2024-02-08 15:58:40

单调栈总结+Leetcode实例

单调栈

1.模型识别

  1. 求左边第一个比当前数小/大的数
  2. 求右边第一个比当前数小/大的数
  3. 向前看比当前数都大/小的连续长度–等价于1
  4. 向后看比当前数都大/小的连续长度–等价于2

2.原理

例：求左边第一个比当前数小的数
维护一个单调递增栈，如果i<j, a[i] > a[j], 那么在j以后，a[i]永远不会作为答案被输出，因为a[j]比a[i]小，任意一个j以后的数向前看的时候会被a[j]挡住，看不到a[i]。

3.模板

#include <iostream>
using namespace std;
const int N = 100010;
int stk[N], tt;

int main() {
    int n;
    int x;
    scanf("%d", &n);
    while (n--) {
        cin >> x;
        while (stk[tt] >= x) tt--;
        if (tt) cout << stk[tt] << " ";
        else cout << -1 << " ";
        stk[++tt] = x;
    }
    return 0;
}

4.例题基础版

1) LeetCode 739. 每日温度

  • 题目：请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。
    例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

  • 思路：模板题，找右边第一个大于当前元素的位置，栈存储位置即可。

  • 答案:

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& t) {
        vector<int> res(t.size());
        stack<int> st;
        for (int i = t.size() - 1; i >= 0; i--) {
            while (st.size() && t[i] >= t[st.top()]) st.pop();
            if (st.size()) res[i] = st.top() - i;
            st.push(i);
        }
        return res;
    }
};

2)LeetCode 496. 下一个更大元素 I

  • 题目：给你两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。
    nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。
  • 思路：对于nums2的每个元素，用vector记录右边第一个比他大的元素，然后建立哈希表存储这个结果，然后遍历nums1查找每个元素右边第一个比它大的元素。
  • 答案:
class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> hash; //用unordered_map哈希表来存，降低时间复杂度
        vector<int> res;
        stack<int> st;
        for (int i = nums2.size() - 1; i >= 0; i--) {
            int cur = nums2[i]; //该循环中反复使用的数，存下来降低时间复杂度
            while(st.size() && st.top() <= cur) st.pop();
            if(st.size()) hash[cur] = st.top();
            else hash[cur] = -1;
            st.push(cur);
        }
        for (int i = 0; i < nums1.size(); i++) {
            res.push_back(hash[nums1[i]]);
        }
        return res;
    }
};

3)LeetCode 503. 下一个更大元素 II

  • 题目：给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。
  • 思路：破链成环，在原链后面把整个链复制一遍。新的链包含了答案需要的所有路径。
  • 答案:
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        stack<int> st;
        int n = nums.size();
        vector<int> res(n);
        nums.insert(nums.end(), nums.begin(), nums.end());
        for (int i = nums.size() - 1; i >= 0; i--) {
            int cur = nums[i];
            while (st.size() && cur >= st.top()) st.pop();
            if (i < n) { //遍历到对应元素再记录
                if (st.empty()) res[i] = -1;
                else {
                    res[i] = st.top();
                }
            }
            st.push(cur);
        }
        return res;

    }
};

4)LeetCode 901. 股票价格跨度

  • 题目：编写一个 StockSpanner 类，它收集某些股票的每日报价，并返回该股票当日价格的跨度。
    今天股票价格的跨度被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。
    例如，如果未来7天股票的价格是 [100, 80, 60, 70, 60, 75, 85]，那么股票跨度将是 [1, 1, 1, 2, 1, 4, 6]。
  • 思路：求过去小于等于今天价格的最大连续日数，转换成求过去第一个大于今天的位置。这道题要返回距离上一个大于今天数的位置，而不是数本身，并且写的是迭代器，得不到全部序列，所以需要存一下pair。
  • 答案:
class StockSpanner {
public:
    StockSpanner() {
        
    }
    stack<pair<int, int>> st;

    int next(int price) {
        int w = 1;
        while(!st.empty() && st.top().first <= price) {
            w += st.top().second;
            st.pop();
        }
        st.push(pair<int, int>(price, w));
        return w;
    }
};

5)LeetCode 1019. 链表中的下一个更大节点

  • 题目：给出一个以头节点 head 作为第一个节点的链表。链表中的节点分别编号为：node_1, node_2, node_3, … 。
    每个节点都可能有下一个更大值（next larger value）：对于 node_i，如果其 next_larger(node_i) 是 node_j.val，那么就有 j > i 且 node_j.val > node_i.val，而 j 是可能的选项中最小的那个。如果不存在这样的 j，那么下一个更大值为 0 。
    返回整数答案数组 answer，其中 answer[i] = next_larger(node_{i+1}) 。

  • 思路：我是先把链表存成了vector，然后用传统模板做的，但是似乎有遍历一遍的做法，空间复杂度会更低。到时候看Y总会不会讲啦啦啦。

  • 答案:

class Solution {
public:
    vector<int> nextLargerNodes(ListNode* head) {
        stack<int> st;
        vector<int> res;
        ListNode* cur = head;
        while(cur->next != NULL) {
            res.push_back(cur->val);
            cur = cur->next;
        }
        res.push_back(cur->val);
        vector<int> ans(res.size(), 0);
        for (int i = res.size() - 1; i >= 0; i--) {
            while (!st.empty() && res[i] >= st.top()) st.pop();
            if (!st.empty()) ans[i] = st.top();
            st.push(res[i]);
        }
        return ans;
    }
};

5.例题提高版

1)LeetCode 84. 柱状图中最大的矩形

  • 题目：给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
    求在该柱状图中，能够勾勒出来的矩形的最大面积。

  • 思路：枚举每条边做上边界的情况，找出每条柱子左边和右边第一个低于它的柱子，算出它做上边界的面积。可以做常数优化：不用遍历两遍，在求左边界的同时，如果某条边出栈，意味着右边出现了第一个小于等于它的柱子，虽然我们想要的是小于它的柱子，但是在下一个等于它的柱子处可以求得它本身的正确答案，所以是正确的。

  • 答案:
    遍历两遍

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> st1;
        int n = heights.size();
        vector<int> res1(n), res2(n);
        for (int i = 0; i < heights.size(); i++) {
            while(!st1.empty() && heights[i] <= heights[st1.top()]) st1.pop();
            if(!st1.empty()) res1[i] = st1.top();
            else res1[i] = -1;
            st1.push(i);
        }
        st1 = stack<int>();
        for (int i = n - 1; i >= 0; i--) {
            while(!st1.empty() && heights[i] <= heights[st1.top()]) st1.pop();
            if(!st1.empty()) res2[i] = st1.top();
            else res2[i] = n;
            st1.push(i);
        }
        int m = 0;
        for (int i = 0; i < heights.size(); i++) {
            m  = max(m, heights[i] * (res2[i] - res1[i] - 1));
        }
        return m;
    }
};

优化：虽然是常数优化，但是时间复杂度排名一下子提到90%以上了。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> st1;
        int n = heights.size();
        vector<int> res1(n, -1), res2(n, n);
        for (int i = 0; i < heights.size(); i++) {
            while(!st1.empty() && heights[i] <= heights[st1.top()]) {
                res2[st1.top()] = i;
                st1.pop();
            }
            if(!st1.empty()) res1[i] = st1.top();
            st1.push(i);
        }
        int m = 0;
        for (int i = 0; i < heights.size(); i++) {
            m  = max(m, heights[i] * (res2[i] - res1[i] - 1));
        }
        return m;
    }
};

2)LeetCode 42. 接雨水

  • 题目：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

  • 思路：我开始又找到了两边高于当前柱子的位置，然后枚举每条边当下边界的情况算，总的来说需要考虑的事情多一些，而且需要遍历两遍。只遍历一遍的最优解是出现凹槽的右端点再加上这段面积，和5一样，利用的原理是：当一个数出栈时说明找到了右边大于当前的数，这里注意没有取等号。

  • 答案:

class Solution {
public:
    int trap(vector<int>& h) {
        stack<int> st1;
        int n = h.size();
        if (n == 0) return 0;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            while(!st1.empty() && h[i] > h[st1.top()]) {
                int bot = st1.top();
                st1.pop();
                if (st1.empty()) break;
                int left = st1.top();
                ans = ans +  (min(h[left], h[i]) - h[bot]) * (i - left - 1);
            }
            st1.push(i);
        }
        return ans;
    }
};
上一篇：佛祖保佑永无BUG代码注释


下一篇：彻底弄懂vue接口代理