首页 > 其他分享 >单调栈

单调栈

时间：2024-08-31 22:37:50浏览次数：2  
标签：popIndex int res top stk include 单调

单调栈

  • 经典用法：在数组中当前元素的两侧找第一个比当前元素更大（更小）的数在哪

  • 维持求解答案的可能性

    1. 单调栈里的所有对象按照规定好的单调性来组织

    2. 当某个对象进入单调栈时，会从栈顶开始依次淘汰单调栈里对后续求解答案没有帮助的对象

    3. 每个对象从栈顶弹出时结算当前对象参与的答案，随后这个对象不再参与后续求解答案的过程

单调栈结构(进阶)

#include <iostream>
#include <vector>
#include <map>
#include <stack>

using namespace std;

// 给定一个可能含有重复值的数组 arr，找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置。
// 返回所有位置相应的信息。
int main() {
    // 输入
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; ++i) cin >> arr[i];

    // 记录下标 i 处的元素，两侧第一个比 arr[i] 小的元素位置
    vector<pair<int, int>> res(n);
    // 单调增栈，栈底到栈顶递增，记录元素下标
    stack<int> stk;

    // 遍历
    for (int i = 0; i < n; ++i) {
        // 栈不空且栈顶元素大于等于当前值时，弹出栈顶，结算两侧第一个更小的位置
        while (!stk.empty() && arr[stk.top()] >= arr[i]) {
            int popIndex = stk.top();
            stk.pop();
            // 左侧第一个更小为之前被压在元素下面的那个元素，也就是当前元素弹出后的新栈顶
            res[popIndex].first = stk.empty() ? -1 : stk.top();
            // 右侧第一个更小就是迫使他出栈的当前元素（arr 中有重复元素时，这个记录后续还需修正）
            res[popIndex].second = i;
        }
        stk.emplace(i);
    }

    // 清算单调栈中剩余元素
    while (!stk.empty()) {
        int popIndex = stk.top();
        stk.pop();
        // 左侧第一个更小为之前被压在元素下面的那个元素，也就是当前元素弹出后的新栈顶
        res[popIndex].first = stk.empty() ? -1 : stk.top();
        // 右侧第一个更小不存在
        res[popIndex].second = -1;
    }

    // 修正
    for (int i = n - 2; i >= 0; i--)
        // 右侧第一个更小存在且值和当前值相等时，修正为右侧的右侧
        if (res[i].second != -1 && (arr[res[i].second] == arr[i]))
            res[i].second = res[res[i].second].second;

    // 输出
    for (int i = 0; i < n; ++i)
        cout << res[i].first << " " << res[i].second << endl;
}

739. 每日温度

#include <iostream>
#include <vector>
#include <map>
#include <stack>

using namespace std;

class Solution {
public:
    // 右侧第一个更大
    vector<int> dailyTemperatures(vector<int> &temperatures) {
        vector<int> res(temperatures.size());
        // 单调不增栈，从栈底到栈顶严格非递增
        stack<int> stk;

        for (int i = 0; i < temperatures.size(); ++i) {
            // 栈不空且栈顶比当前元素小，栈顶出栈并记录右侧第一个更大
            while (!stk.empty() && temperatures[stk.top()] < temperatures[i]) {
                int popIndex = stk.top();
                stk.pop();
                // 右侧第一个更大就是当前元素
                res[popIndex] = i - popIndex;
            }
            stk.emplace(i);
        }

        while (!stk.empty()) {
            int popIndex = stk.top();
            stk.pop();
            // 不存在右侧第一个更大
            res[popIndex] = 0;
        }

        return res;
    }
};

907. 子数组的最小值之和

#include <iostream>
#include <vector>
#include <map>
#include <stack>

using namespace std;

class Solution {
public:
    int sumSubarrayMins(vector<int> &arr) {
        const int MOD = 1e9 + 7;
        const int len = arr.size();
        long res = 0;
        // 栈底到栈顶递增
        stack<int> stk;

        // 遍历
        for (int i = 0; i < len; ++i) {
            // 每次栈顶出栈，都要结算左右第一个更小的位置
            while (!stk.empty() && (arr[stk.top()] >= arr[i])) {
                int popIndex = stk.top();
                stk.pop();
                int left = stk.empty() ? -1 : stk.top();
                // arr[popIndex] 必须包含在连续子数组(l, r)内，l 为左侧第一个更小的，r 为右侧第一个更大的
                // popIndex - left 为子数组开头位置的可能总数，i - popIndex 为结尾总数
                long tempRes = (popIndex - left) * (i - popIndex) * (long) arr[popIndex];
                res = (res + tempRes) % MOD;
            }
            stk.emplace(i);
        }
        // 清算栈中剩余
        while (!stk.empty()) {
            int popIndex = stk.top();
            stk.pop();
            int left = stk.empty() ? -1 : stk.top();
            long tempRes = (popIndex - left) * (len - popIndex) * (long) arr[popIndex];
            res = (res + tempRes) % MOD;
        }

        return (int) res;
    }
};

84. 柱状图中最大的矩形

#include <iostream>
#include <vector>
#include <map>
#include <stack>

using namespace std;

class Solution {
public:
    int largestRectangleArea(vector<int> &heights) {
        int len = heights.size();
        int res = 0;
        // 栈底到栈顶递增
        stack<int> stk;

        // 以当前位置的高度为矩形的高度，向两侧扩展，直到两侧第一个更低的位置，构成矩形的宽
        for (int i = 0; i < len; ++i) {
            while (!stk.empty() && (heights[stk.top()] >= heights[i])) {
                int popIndex = stk.top();
                stk.pop();
                int left = stk.empty() ? -1 : stk.top();
                int width = i - left - 1;
                res = max(res, heights[popIndex] * width);
            }
            stk.emplace(i);
        }

        while (!stk.empty()) {
            int popIndex = stk.top();
            stk.pop();
            int left = stk.empty() ? -1 : stk.top();
            int width = len - left - 1;
            res = max(res, heights[popIndex] * width);
        }

        return res;
    }
};

85. 最大矩形

#include <iostream>
#include <vector>
#include <map>
#include <stack>

using namespace std;

class Solution {
public:
    int largestRectangleArea(vector<int> &heights) {
        int len = heights.size();
        int res = 0;
        // 栈底到栈顶递增
        stack<int> stk;

        // 以当前位置的高度为矩形的高度，向两侧扩展，直到两侧第一个更低的位置，构成矩形的宽
        for (int i = 0; i < len; ++i) {
            while (!stk.empty() && (heights[stk.top()] >= heights[i])) {
                int popIndex = stk.top();
                stk.pop();
                int left = stk.empty() ? -1 : stk.top();
                int width = i - left - 1;
                res = max(res, heights[popIndex] * width);
            }
            stk.emplace(i);
        }

        while (!stk.empty()) {
            int popIndex = stk.top();
            stk.pop();
            int left = stk.empty() ? -1 : stk.top();
            int width = len - left - 1;
            res = max(res, heights[popIndex] * width);
        }

        return res;
    }

    int maximalRectangle(vector<vector<char>> &matrix) {
        int res = 0;
        int row = matrix.size();
        int column = matrix.at(0).size();
        // 压缩数组：记录当前行为底，往上数连续 1 的总数
        vector<int> heights(column, 0);

        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < column; ++j)
                heights[j] = matrix[i][j] == '1' ? (heights[j] + 1) : 0;
            // 计算以 i 行为底构成的最大矩形
            res = max(res, largestRectangleArea(heights));
        }

        return res;
    }
};

962. 最大宽度坡

#include <iostream>
#include <vector>
#include <map>
#include <stack>

using namespace std;

class Solution {
public:
    int maxWidthRamp(vector<int> &nums) {
        int res = 0;
        // 栈底到栈顶递减
        stack<int> stk;

        for (int i = 0; i < nums.size(); ++i) {
            // 比栈顶小才会进栈
            if (stk.empty() || nums[stk.top()] > nums[i])
                stk.emplace(i);
        }

        // 从右往左遍历，可以构造出最大宽度
        for (int i = nums.size() - 1; i >= 0; i--) {
            // 栈不空，且栈顶到当前元素能构成坡
            while (!stk.empty() && nums[stk.top()] <= nums[i]) {
                // 更新最大宽度
                res = max(res, i - stk.top());
                stk.pop();
            }
        }
        return res;
    }
};

316. 去除重复字母

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <stack>

using namespace std;

class Solution {
public:
    string removeDuplicateLetters(string s) {
        // 记录词频
        unordered_map<char, int> freq;
        // 记录有没有进栈
        unordered_set<char> enter;
        // 栈底到栈顶递增
        stack<char> stk;
        // 统计字符频率
        for (auto& ch : s) freq[ch]++;

        for (auto& ch : s) {
            // 不在栈中才进行
            if (enter.find(ch) == end(enter)) {
                while (!stk.empty() && stk.top() > ch && freq[stk.top()] > 0) {
                    // 出栈
                    enter.erase(stk.top());
                    stk.pop();
                }
                // 进栈
                stk.emplace(ch);
                enter.insert(ch);
            }
            // 减少词频
            freq[ch]--;
        }

        string res;
        while (!stk.empty()) {
            res.insert(0, 1, stk.top());
            stk.pop();
        }
        return res;
    }
};

大鱼吃小鱼

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

int main() {
    int len;
    cin >> len;
    vector<int> arr(len);
    for (int i = 0; i < len; ++i) cin >> arr[i];

    // <鱼大小, 下标>，栈底到栈顶按照第一维递减
    stack<pair<int, int>> stk;
    int res = 0;
    // 从右往左遍历
    for (int i = len - 1; i >= 0; i--) {
        int curTurns = 0;
        while (!stk.empty() && stk.top().first < arr[i]) {
            curTurns = max(curTurns + 1, stk.top().second);
            stk.pop();
        }
        stk.emplace(make_pair(arr[i], curTurns));
        res = max(res, curTurns);
    }

    cout << res;
}

1504. 统计全 1 子矩形

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

class Solution {
public:
    // 比如
    //              1
    //              1
    //              1         1
    //    1         1         1
    //    1         1         1
    //    1         1         1
    //
    //    3  ....   6   ....  8
    //   left      cur        i
    // 如上图，假设6位置从栈中弹出，6位置的高度为6(上面6个1)
    // 6位置的左边、离6位置最近、且小于高度6的是3位置(left)，3位置的高度是3
    // 6位置的右边、离6位置最近、且小于高度6的是8位置(i)，8位置的高度是4
    // 此时我们求什么？
    // 1) 求在4~7范围上必须以高度6作为高的矩形有几个？
    // 2) 求在4~7范围上必须以高度5作为高的矩形有几个？
    // 也就是说，<=4的高度一律不求，>6的高度一律不求！
    // 其他位置也会从栈里弹出，等其他位置弹出的时候去求！
    // 那么在4~7范围上必须以高度6作为高的矩形有几个？如下：
    // 4..4  4..5  4..6  4..7
    // 5..5  5..6  5..7
    // 6..6  6..7
    // 7..7
    // 10个！什么公式？
    // 4...7范围的长度为4，那么数量就是 : 4*5/2
    // 同理在4~7范围上，必须以高度5作为高的矩形也是这么多
    // 所以cur从栈里弹出时产生的数量 :
    // (cur位置的高度-Max{left位置的高度,i位置的高度}) * ((i-left-1)*(i-left)/2)
    int countFromBottom(stack<int> &stk, vector<int> &heights, int columns) {
        int res = 0;
        for (int i = 0; i < columns; ++i) {
            while (!stk.empty() && heights[stk.top()] >= heights[i]) {
                int cur = stk.top();
                stk.pop();
                if (heights[cur] > heights[i]) {
                    // 只有height[cur] > height[i]才结算
                    // 如果是因为height[cur]==height[i]导致cur位置从栈中弹出
                    // 那么不结算！等i位置弹出的时候再说！
                    int left = stk.empty() ? -1 : stk.top();
                    int len = i - left - 1;
                    int bottom = max(left == -1 ? 0 : heights[left], heights[i]);
                    res += (heights[cur] - bottom) * len * (len + 1) / 2;
                }
            }
            stk.emplace(i);
        }

        while (!stk.empty()) {
            int cur = stk.top();
            stk.pop();
            int left = stk.empty() ? -1 : stk.top();
            int len = columns - left - 1;
            int down = left == -1 ? 0 : heights[left];
            res += (heights[cur] - down) * len * (len + 1) / 2;
        }
        return res;
    }

    int numSubmat(vector<vector<int>> &mat) {
        int res = 0;
        int rows = mat.size();
        int columns = mat.at(0).size();
        stack<int> stk;
        vector<int> heights(columns, 0);
        for (int i = 0; i < rows; ++i) {
            // 压缩数组
            for (int j = 0; j < columns; ++j)
                heights[j] = mat[i][j] == 1 ? heights[j] + 1 : 0;
            res += countFromBottom(stk, heights, columns);
        }

        return res;
    }
};

标签：popIndex,int,res,top,stk,include,单调
From： https://www.cnblogs.com/sprinining/p/18390871

相关文章

  • 738. 单调递增的数字(leetcode)
    https://leetcode.cn/problems/monotone-increasing-digits/description/classSolution{publicintmonotoneIncreasingDigits(intn){//返回单调递增的最大数字//思路比较巧妙的贪心题,需要仔细考虑两个相邻位之间的比较//一旦发现有前一......
  • 单调队列--滑动窗口最大值（leetcode23）
    目录一、单调队列介绍二、题目应用1.题目描述2.解题碎碎念3.代码示例三、扩展1.与优先队列区别2.单调队列其他题目一、单调队列介绍单调队列是一种特殊的队列数据结构，它能够在常数时间内找到队列中的最值。单调队列可以用来解决一些与最值相关的问题，例如滑动窗口最......
  • P5788 【模板】单调栈
    P5788【模板】单调栈传送门题目描述给出项数为\(n\)的整数数列\(a_{1\dotsn}\)。定义函数\(f(i)\)代表数列中第\(i\)个元素之后第一个大于\(a_i\)的元素的下标，即\(f(i)=\min_{i<j\leqn,a_j>a_i}\{j\}\)。若不存在，则\(f(i)=0\)。试求出\(f(1\dotsn)\)。......
  • 线段树维护单调栈——区间查询版本 & 维护递减序列
    这次算是完全搞懂了吧（）（）（#include<bits/stdc++.h>#defineraedread#definecaclcalc#definepbpush_back#definepiipair<int,int>#defineintlonglong#definefifirst#definesesecond#definelsp<<1#definersp<<1|1usingn......
  • LeetCode84(柱状图中最大的矩形)理解单调栈
    1.LeetCode84(柱状图中最大的矩形)给定n个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为1。求在该柱状图中，能够勾勒出来的矩形的最大面积。示例1:输入：heights=[2,1,5,6,2,3]输出：10解释：最大的矩形为图中红色区域，面积为10示例2：输入......
  • 洛谷P10878 [JRKSJ R9] 在相思树下 III && 单调队列
    传送门：P10878[JRKSJR9]在相思树下III将军啊，早卸甲，他还在廿二，等你回家……一道练习单调队列的好题qwq题目意思：很明白了，不再复述。（注意$\foralli$表示对于任意的i，可理解为所有）思路：贪心是很明显的，因为我们要让最后的值最大，首先要把小的值删掉。最后的答案就是进......
  • Little Bird（单调队列优化的DP）
    题目描述有一排\(n\)棵树，第\(i\)棵树的高度是\(d_i\)。有一只鸟要从第\(1\)棵树飞到第\(n\)棵树。如果鸟降落在第\(i\)棵树，那么它下一步可以降落到第\(i+1,i+2,\dots,i+k\)棵树之中的一棵。如果鸟降落到一棵不矮于当前树的树，那么它的劳累值会\(+1\)，否则不会。求劳累值的最小值......
  • Sound（单调队列）
    题目描述第一行有三个整数\(n,m,c(1\leqn\leq10^6,1\leqm\leq10^4,0\leqc\leq10^4)\)。第二行\(n\)个非负整数\(a_1,a_2,\dots,a_n(1\leqa_i\leq10^6)\)。求有多少个i满足[i...i+m-1]区间的极差<=c输出从小到大输出所有满足条件的\(i\)，一行一个。如果没有\(i\)满足条......
  • 单调栈和单调队列优化DP
    单调栈和单调队列优化DPluoguP1725琪露诺一道比较板的题明显是一个DP，则有\[{dp}_i=\max_{j=i-r}^{i-l}dp_j+a_i\]如果暴力则为\(O(n^2)\)但是发现\(\max_{j=i-r}^{i-l}dp_j\)就是单调队列所解决的问题，所以直接单调队列维护即可#include<bits/stdc++.h>#defineFAS......
  • 【模板】单调栈
    洛谷P5788【模板】单调栈单调栈就是使栈内元素单调递增或者单调递减的栈，单调栈也只能在栈顶操作。做一个比喻，比方说：有个集训队招人，一个数代表了一个选手的能力值，先进来的选手年龄会比较大，后面的选手年龄比较小，但是这个集训队没有人数限制，那么如果遇到一个比你小还比你强的人那......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99