「算法刷题」栈运算专项汇总（力扣版）

本文记录作者刷题过程中与栈相关的题目。

一、设计最小栈

剑指 Offer 30. 包含min函数的栈（中等函数）

155. 最小栈（简单难度）

面试题 03.02. 栈的最小值（简单难度）

class MinStack {
public:
    stack<int> stack1;//正常栈，实现栈的正常功能
    stack<int> stack2;//辅助栈，负责实现min函数，入栈时只入比自己栈顶元素小的元素，出栈时和当前元素相等就出栈
    MinStack() {}
    // 入栈
    void push(int val) {
        stack1.push(val);//正常入栈
        // 如果辅助栈为空或者辅助栈栈顶元素比较大，就入栈
        if(stack2.empty()||stack2.top()>=val)stack2.push(val);
    }
    // 出栈
    void pop() {
        int top=stack1.top();
        stack1.pop();// 正常出栈
        // 如果出栈的元素和辅助栈栈顶元素相等
        if(top==stack2.top()) stack2.pop();
    }
    // 获取栈顶元素
    int top() {
        return stack1.top();//正常的栈顶元素
    }
    // 获取最小值
    int getMin() {
        return stack2.top();//辅助栈的栈顶元素
    }
};

二、验证栈序列

剑指 Offer 31. 栈的压入、弹出序列

946. 验证栈序列（中等难度）

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> stk;
        int i=0;
        for(int x:pushed){
            stk.push(x);
            // 循环检查，如果栈顶元素和出栈队列元素相同就出栈
            // 栈内元素用完就继续加
            while(!stk.empty()&&stk.top()==popped[i]){
                stk.pop();
                i++;
            }
        }
        return stk.empty();
    }
};

三、单调栈

剑指 Offer II 039. 直方图最大矩形面积

84. 柱状图中最大的矩形

class Solution {
public:
    /*本题也是一套经典题目，题目容易理解，难点在于分析什么时候勾勒的矩形面积最大？
    思路：
    假设我们考察其中一个柱子，它所能勾勒出的最大矩形面积由左侧柱子和右侧柱子的高度决定：
    若左柱子的高度>当前考察的柱子高度，则向左扩张一个柱子，直至左侧柱子高度<当前柱子高度||左侧无柱子
    若右柱子的高度>当前考察的柱子高度，则向右扩张一个柱子，直至右侧柱子高度<当前柱子高度||右侧无柱子
    此时最大矩形面积=当前柱子的高度*左右最远柱子间的距离
    单调栈的简单思路讲解：https://blog.csdn.net/Zolewit/article/details/88863970*/
    int largestRectangleArea(vector<int>& heights) {
        int res=0;//最大面积
        int n=heights.size();
        // 在原数组左右两侧添加一个0
        vector<int> height(n+2,0);
        for(int i=1;i<n+1;i++){
            height[i]=heights[i-1];
        }
        stack<int> stk;// 单调栈，保存元素索引
        for(int i=0;i<n+2;i++){
            // 当前入栈元素为height[i]，将栈中所有比height[i]大的元素出栈
            while(!stk.empty()&&height[i]<height[stk.top()]){
                // 出栈
                int index=stk.top();
                stk.pop();
                // 此时，height[index]的下一个更小元素是height[i]，上一个更小元素是height[stk.top()]
                int hig=height[index];//高=height[index]，其随着出栈而不断变化
                int wid=i-stk.top()-1;//宽=[stk.top(),i]=i-stk.top()-1，右边界是定值，左边界是变量
                res =max(res,hig*wid);//完全覆盖第index个柱子的最大矩形的面积
            }
            stk.push(i);
        }
        return res;
    }
};

85. 最大矩形

剑指 Offer II 040. 矩阵中最大的矩形

class Solution {
public:
    /*每一层看作是柱状图，可以套用84题柱状图的最大面积。
    第一层柱状图的高度["1","0","1","0","0"]，最大面积为1；
    第二层柱状图的高度["2","0","2","1","1"]，最大面积为3；
    第三层柱状图的高度["3","1","3","2","2"]，最大面积为6；
    第四层柱状图的高度["4","0","0","3","0"]，最大面积为4；*/
    int maximalRectangle(vector<vector<char>>& matrix) {
        if (matrix.size() == 0 || matrix[0].size() == 0) {
            return 0;
        }
        int col = matrix.size();
        int row = matrix[0].size();
        vector<int>heights(row);
        int ans = 0;
        for (int i = 0; i < col; i++) {
            for (int j = 0; j < row; j++) {
                if (matrix[i][j] == '1') {
                    heights[j] += 1;
                } else {
                    heights[j] = 0;
                }
            }
            ans = max(ans, largestRectangleArea(heights));
        }
        return ans;
    }
    int largestRectangleArea(vector<int>& heights) {
        int res=0;//最大面积
        int n=heights.size();
        // 在原数组左右两侧添加一个0
        vector<int> height(n+2,0);
        for(int i=1;i<n+1;i++){
            height[i]=heights[i-1];
        }
        stack<int> stk;// 单调栈，保存元素索引
        for(int i=0;i<n+2;i++){
            // 当前入栈元素为height[i]，将栈中所有比height[i]大的元素出栈
            while(!stk.empty()&&height[i]<height[stk.top()]){
                // 出栈
                int index=stk.top();
                stk.pop();
                // 此时，height[index]的下一个更小元素是height[i]，上一个更小元素是height[stk.top()]
                int hig=height[index];//高=height[index]，其随着出栈而不断变化
                int wid=i-stk.top()-1;//宽=[stk.top(),i]=i-stk.top()-1，右边界是定值，左边界是变量
                res =max(res,hig*wid);//完全覆盖第index个柱子的最大矩形的面积
            }
            stk.push(i);
        }
        return res;
    }
};