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();//辅助栈的栈顶元素
    }
};

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();
    }
};

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;
    }
};