剑指offer刷题（一）（1-20）题

忘是亡心i 2021-12-17 13:37 383阅读 0赞

由于之前要准备paper以及研电赛，好久没有更新了，paper已经投了个会议了，然后研电赛只拿到了西北赛区人工智能组的二等奖，没能晋级国赛有点遗憾。废话不多说，准备秋招了，刷点编程题练练手。每题都有思路，有些是参考的，会注明出处。题目顺序参照牛客网，语言选择C++，因为C++速度确实快。

### 1 二维数组的查找 ###

在一个二维数组中（每个一维数组的长度相同），**每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序**。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

class Solution {
    public:
        /**
        利用
        每一行都按照从左到右递增的顺序排序
        每一列都按照从上到下递增的顺序排序
        如果 xx 小于target，则 xx 左边的数一定都小于target，我们可以直接排除当前一整行的数；
        如果 xx 大于target，则 xx 下边的数一定都大于target，我们可以直接排序当前一整列的数；
        参考：https://www.acwing.com/solution/AcWing/content/702/
        */
        bool Find(int target, vector<vector<int> > a) {
            //如果a为空 直接返回false
            if(a.empty()||a[0].empty())return false;
            int i = 0, j = a[0].size() - 1;//要从右上角往左下角找
            while(i < a.size() && j >= 0){
                if(a[i][j] == target)return true;//找到直接返回
                if(a[i][j] > target) j--;//列往左边移动
                else i++;//行往下移动找
            }
            return false;
        }
    };

### 2 替换空格 ###

请实现一个函数，**将一个字符串中的每个空格替换成“%20”**。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

class Solution {
    public:
    	void replaceSpace(char *str,int length) {
            if(str == NULL) return; //如果是空 直接返回
            //空格数 原始串的长 新串的长
            int blanks = 0, len = 0, newlen = 0;
            for(int i = 0;str[i]!='\0';i++){
                len++;
                if(str[i]==' ')
                    blanks++;
            }
            //新串的长 每次替换 多增加两个字符
            newlen = len + 2*blanks;
            
            //如果新串的长大于length 直接返回
            if(newlen + 1 > length)return;
            
            //str1指针指向旧串的最后一个字符
            char * str1 = str + len;
            
            //str2指针指向新串的最后一个字符
            char * str2 = str + newlen;
            
            //从后向前自制旧串 并替换空格
            while(str1 != str2){
                if(*str1 == ' '){
                    *str2 -- = '0';
                    *str2 -- = '2';
                    *str2 -- = '%';
                }
                else
                    *str2 -- = *str1;
                --str1;
            }
            
    	}
    };

### 3 从尾到头打印链表 ###

输入一个链表，按**链表值从尾到头的顺序**返回一个ArrayList。

/**
    *  struct ListNode {
    *        int val;
    *        struct ListNode *next;
    *        ListNode(int x) :
    *              val(x), next(NULL) {
    *        }
    *  };
       没有什么要求，直接遍历一次链表，每次向vector.begin()处插入就行了
    */
    class Solution {
    public:
        vector<int> printListFromTailToHead(ListNode* head) {
            vector<int> res;
            while(head){
                res.insert(res.begin(),head->val);
                head = head->next;
            }
            return res;
        }
    };

### 4 重建二叉树 ###

输入某二叉树的**前序遍历和中序遍历的结果**，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{1,2,4,7,3,5,6,8\}和中序遍历序列\{4,7,2,1,5,3,8,6\}，则重建二叉树并返回。

/**
     * Definition for binary tree
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     算法
    (递归) O(n)O(n)
    递归建立整棵二叉树：先递归创建左右子树，然后创建根节点，并让指针指向两棵子树。
    
    具体步骤如下：
    
    先利用前序遍历找根节点：前序遍历的第一个数，就是根节点的值；
    在中序遍历中找到根节点的位置 kk，则 kk 左边是左子树的中序遍历，右边是右子树的中序遍历；
    假设左子树的中序遍历的长度是 ll，则在前序遍历中，根节点后面的 ll 个数，是左子树的前序遍历，剩下的数是右子树的前序遍历；
    有了左右子树的前序遍历和中序遍历，我们可以先递归创建出左右子树，然后再创建根节点；
    
    时间复杂度分析
    我们在初始化时，用哈希表(unordered_map<int,int>)记录每个值在中序遍历中的位置，
    这样我们在递归到每个节点时，在中序遍历中查找根节点位置的操作，
    只需要 O(1)O(1) 的时间。此时，创建每个节点需要的时间是 O(1)O(1)，所以总时间复杂度是 O(n)O(n)。
    
    参考：https://www.acwing.com/solution/AcWing/content/706/
     */
    class Solution {
    public:
        
        TreeNode* dfs(unordered_map<int,int> &pos,vector<int> &pre, vector<int> &vin, int pl, int pr, int vl, int vr){
            if(pl > pr)return 0;
            int k = pos[pre[pl]] - vl ;//k的左边为左子树，右边为右子树
            TreeNode* root = new TreeNode(pre[pl]);//创建根
            root->left = dfs(pos, pre, vin, pl + 1, pl + k, vl, vl + k - 1);//递归创建左子树，更新下次pre和vin
            root->right = dfs(pos, pre, vin, pl + k + 1, pr,  vl + k + 1, vr);//递归创建右子树，更新下次pre和vin
            return root;
        }
        TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
            int n = pre.size();
            unordered_map<int,int> pos;//记录中序遍历的位置
            for(int i = 0; i < n; i++){
                pos[vin[i]] = i;
            }
            return dfs(pos, pre, vin, 0, n - 1, 0, n - 1);
        }
        
    };

### 5 用栈实现队列 ###

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

/**
    用两个栈 一个缓存用
    当操作时 先把主栈的数据先全部放到缓存
    然后再pop
    完成后放到主栈
    **/
    
    class Solution
    {
    public:
        void copy(stack<int> &a, stack<int> &b) {
            while (a.size()) {
                b.push(a.top());
                a.pop();
            }
        }
        void push(int node) {
            stack1.push(node);
        }
        int pop() {
            copy(stack1,stack2);
            int res = stack2.top();
            stack2.pop();
            copy(stack2,stack1);
            return res;
        }
    
    private:
        stack<int> stack1;//主栈
        stack<int> stack2;//缓存栈
    };

### 6 旋转数组中最小的数字 ###

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组\{3,4,5,1,2\}为\{1,2,3,4,5\}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

/**
    数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转
    可以看出
    因为旋转前数组是递增
    旋转后有一个这个递增就断了
    相当于找到一个数比第一个数小的情况
    就可以返回这个数
    **/
    class Solution {
    public:
        int minNumberInRotateArray(vector<int> rotateArray) {
            if(!rotateArray.size())return 0;
            int res = rotateArray[0];
            for(int i = 1; i < rotateArray.size(); i++){
                if(rotateArray[i] < res)return rotateArray[i];
            }
            return res;
        }
    };

### 7 斐波那契数列 ###

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39。

/**
    这个没什么好说的
    建议用递推
    除非面试官要求 否则不要用递归
    **/
    class Solution {
    public:
        int Fibonacci(int n) {
            if(n == 0) return 0;
            if(n == 1) return 1;
            int first = 0, second = 1, third = 0;
            while(n--){
                third = first + second;
                first = second;
                second = third;
            }
            return first;
        }
    };

### 8 跳台阶 ###

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

/**
    假设处于当前台阶
    那么从其他台阶跳上来的
    要么从前一个台阶跳上来 要么从前面第2个跳过来
    那么 跳到当前台阶的就有f(n-1) + f(n - 2)
    **/
    class Solution {
    public:
        int jumpFloor(int n) {
            if(n == 1) return 1;
            if(n == 2) return 2;
            return jumpFloor(n - 1) + jumpFloor(n - 2);
        }
    };

### 9 变态跳台阶 ###

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

/**
    因为n级台阶，第一步有n种跳法：跳1级、跳2级、到跳n级
    跳1级，剩下n-1级，则剩下跳法是f(n-1)
    跳2级，剩下n-2级，则剩下跳法是f(n-2)
    所以f(n)=f(n-1)+f(n-2)+...+f(1)
    因为f(n-1)=f(n-2)+f(n-3)+...+f(1)
    所以f(n)=2*f(n-1)
    
    假设
    f(1) = 1;
    所以：
    f(2)=1+f(1)=1+1=2=2^1;
    f(3)=1+f(2)+f(1)=1+2+1=4=2^2;
    f(4)=1+f(3)+f(2)+f(1)=1+4+2+1=8=2^3;
    ......
    归纳：
    f(n) = 2^(n-1);（n>=1的整数）
    **/
    class Solution {
    public:
        int jumpFloorII(int number) {
            int a = 1; 
            return a << (number - 1);//左移乘2 右移除2 如在折半查找中 可以 int mid = (l + r) >> 1
        }
    };

### 10  矩形覆盖 ###

我们可以用2\*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2\*1的小矩形无重叠地覆盖一个2\*n的大矩形，总共有多少种方法？

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70][]

class Solution {
    public:
        int rectCover(int n) {
            if(n == 1) return 1;
            if(n == 2) return 2;
            int first = 1, second = 2, third = 0;
            for(int i=3;i<=n;i++){
                third = first + second;
                first = second;
                second = third;
            }
            return third;
        }
    };

### 11 二进制中1的个数 ###

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

/**
    (位运算) O(logn)O(logn)
    迭代进行如下两步，直到 nn 变成0为止：
    
    如果 nn 在二进制表示下末尾是1，则在答案中加1；
    将 nn 右移一位，也就是将 nn 在二进制表示下的最后一位删掉；
    这里有个难点是如何处理负数。
    在C++中如果我们右移一个负整数，系统会自动在最高位补1，这样会导致 nn 永远不为0，就死循环了。
    解决办法是把 nn 强制转化成无符号整型，这样 nn 的二进制表示不会发生改变，但在右移时系统会自动在最高位补0。
    
    时间复杂度
    每次会将 nn 除以2，最多会除 lognlogn 次，所以时间复杂度是 O(logn)O(logn)。
    
    参考大神：https://www.acwing.com/solution/AcWing/content/732/
    **/
    class Solution {
    public:
         int  NumberOf1(int n) {
             int res = 0;
             unsigned int u = n;
             while(u) res += u & 1, u >>= 1;
             return res;
         }
    };

### 12 数值的整数次方 ###

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

/**
    求幂就是n个base相乘
    如果是负数，取倒数
    **/
    class Solution {
    public:
        double Power(double base, int exponent) {
            double res = 1;
            for(int i = 0; i < abs(exponent); i++)
                res *= base;
            if(exponent < 0)
                res = 1 / res;
            return res;
        }
    };

### 13 调整数组顺序使奇数位于偶数前面 ###

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

/**
    由于没有内存申请限制
    直接用两个队列 一个装奇数 一个装偶数
    依次按放到原来的数组
    **/
    
    class Solution {
    public:
        void reOrderArray(vector<int> &array) {
            queue<int> s1,s2;
            for(auto it: array){
                if(it % 2 == 0)
                    s2.push(it);
                else s1.push(it);
            }
            for(int i = 0; i < array.size(); i++){
                if(!s1.empty()){
                    array[i] = s1.front();
                    s1.pop();
                }
                else{
                    array[i] = s2.front();
                    s2.pop();
                }
            }   
        }
    };

### 14 链表中倒数第k个结点 ###

输入一个链表，输出该链表中倒数第k个结点。

/*
    struct ListNode {
    	int val;
    	struct ListNode *next;
    	ListNode(int x) :
    			val(x), next(NULL) {
    	}
        先算出链表的长度n
        倒数第k个结点即为顺数第n-k个结点
        
        
    };*/
    class Solution {
    public:
        ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
            int len = 0;
            auto cur = pListHead;
            while(cur){
                len++;
                cur = cur->next;
            }
            if(pListHead == NULL || k > len || k < 1)return NULL;
            int i = len - k;
            cur = pListHead;
            while(i--){
                cur = cur->next;
            }
            return cur;
        }
    };

### 15 反转链表 ###

输入一个链表，反转链表后，输出新链表的表头

/*
    struct ListNode {
    	int val;
    	struct ListNode *next;
    	ListNode(int x) :
    			val(x), next(NULL) {
    	}
    };*/
    class Solution {
    public:
    
        ListNode* ReverseList(ListNode* pHead) {
            ListNode *pre = NULL, *next = NULL;
            
            while(pHead){
                //做循环，如果当前节点不为空的话，始终执行此循环，此循环的目的就是让当前节点从指向next到指向pre
                //如此就可以做到反转链表的效果
                //先用next保存head的下一个节点的信息，保证单链表不会因为失去head节点的原next节点而就此断裂
                next = pHead->next;//记录当前结点的下一个结点
    
                //保存完next，就可以让head从指向next变成指向pre了
                pHead->next = pre;
    
                //head指向pre后，就继续依次反转下一个节点
                //让pre，head，next依次向后移动一个节点，继续下一次的指针反转
                pre = pHead;
                pHead = next;
            }
            //如果head为null的时候，pre就为最后一个节点了，但是链表已经反转完毕，pre就是反转后链表的第一个节点
            //直接输出pre就是我们想要得到的反转后的链表
            return pre;
        }
    };

### 16 合并两个有序链表 ###

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

/*
    struct ListNode {
    	int val;
    	struct ListNode *next;
    	ListNode(int x) :
    			val(x), next(NULL) {
    	}
    };
    没有什么可说的
    就像合并两个有序数组
    */
    class Solution {
    public:
        ListNode* Merge(ListNode* p1, ListNode* p2)
        {
            auto d = new ListNode(-1);//虚拟头结点
            auto t = d;
            while(p1&&p2){
                if(p1->val < p2->val){//小的先排
                    t->next = p1;
                    p1 = p1->next;
                    t = t->next;
                }
                else{
                    t->next = p2;
                    p2 = p2->next;
                    t = t->next;
                }
                    
            }
            if(p1)t->next = p1;//如果还有直接接到t的屁股后面
            if(p2)t->next = p2;
            return d->next;
        }
    };

### 17 树的子结构 ###

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

/*
    struct TreeNode {
    	int val;
    	struct TreeNode *left;
    	struct TreeNode *right;
    	TreeNode(int x) :
    			val(x), left(NULL), right(NULL) {
    	}
        
    算法
    (二叉树，递归) O(nm)O(nm)
    代码分为两个部分：
    
    遍历树A中的所有非空节点R；
    判断树A中以R为根节点的子树是不是包含和树B一样的结构，且我们从根节点开始匹配；
    对于第一部分，我们直接递归遍历树A即可，遇到非空节点后，就进行第二部分的判断。
    
    对于第二部分，我们同时从根节点开始遍历两棵子树：
    
    如果树B中的节点为空，则表示当前分支是匹配的，返回true；
    如果树A中的节点为空，但树B中的节点不为空，则说明不匹配，返回false；
    如果两个节点都不为空，但数值不同，则说明不匹配，返回false；
    否则说明当前这个点是匹配的，然后递归判断左子树和右子树是否分别匹配即可；
    时间复杂度
    最坏情况下，我们对于树A中的每个节点都要递归判断一遍，每次判断在最坏情况下需要遍历完树B中的所有节点。
    所以时间复杂度是 O(nm)O(nm)，其中 nn 是树A中的节点数， mm 是树B中的节点数。
    
    
    参考大神：https://www.acwing.com/solution/AcWing/content/745/
    
    };*/
    class Solution {
    public:
        bool isSubtree(TreeNode* r1, TreeNode* r2){
            if(!r2)return true;
            if(!r1 || r1->val != r2->val)return false;
            return isSubtree(r1->left, r2->left) && isSubtree(r1->right, r2->right);
        }
        bool HasSubtree(TreeNode* r1, TreeNode* r2)
        {
            if(!r1 || !r2)return false;
            if(isSubtree(r1, r2))return true;
            return HasSubtree(r1->left, r2) || HasSubtree(r1->right, r2);
        }
    };

### 18 二叉树的镜像 ###

操作给定的二叉树，将其变换为源二叉树的镜像。

输入描述:

二叉树的镜像定义：源二叉树 
        	    8
        	   /  \
        	  6   10
        	 / \  / \
        	5  7 9 11
        	镜像二叉树
        	    8
        	   /  \
        	  10   6
        	 / \  / \
        	11 9 7  5

/*
    没什么好说的
    直接交换当前结点的左右孩子
    如果当前结点还有左右孩子
    分别递归交换
    直到递归结束
    struct TreeNode {
    	int val;
    	struct TreeNode *left;
    	struct TreeNode *right;
    	TreeNode(int x) :
    			val(x), left(NULL), right(NULL) {
    	}
    };*/
    class Solution {
    public:
        void Mirror(TreeNode *r) {
            if(!r)return;//没有左右孩子则直接返回
            swap(r->left,r->right);//交换左右孩子
            Mirror(r->left);//递归，继续遍历左子树
            Mirror(r->right);//递归，继续遍历右子树
        }
    };

### 19 顺时针打印矩阵 ###

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

/**
    分别得到行和列的开始和末尾索引
    首先遍历完当前行后 开始行++
    然后列从开始行索引开始遍历后 列--
    末尾行从末尾列往回遍历
    开始列从末尾行到开始行往回遍历
    直到list长度和size一样 结束循环
    
    由于没有其他空间，不算题目要的list的话 空间复杂度O(1) 时间复杂度O(n^2)
    
    **/
    class Solution {
    public:
        vector<int> printMatrix(vector<vector<int> > matrix) {
            vector<int> list;
            if(matrix.size() == 0) return list;
            //水平行的最开始的索引 和 最后的索引 
            int h_first_index = 0, h_last_index = matrix.size() - 1;
            //垂直列的最开始的索引 和 最后的索引 
            int v_first_index = 0, v_last_index = matrix[0].size() - 1;
            //数组的长度
            int size = (h_last_index + 1)*(v_last_index + 1);
            //是否遍历结束
            bool flag = true;
            
            while(flag){
                // 先算开始第一行
                for(int i = v_first_index;i <= v_last_index;i++) {
                    list.push_back(matrix[h_first_index][i]);
                    if(list.size() >= size){
                        flag = false;
                        break;
                    }
                }
                h_first_index ++;
                if(list.size() >= size){
                    break;
                }
                // 再算最后一列
                for(int i=h_first_index;i<=h_last_index;i++) {
                    list.push_back(matrix[i][v_last_index]);
                    if(list.size() >= size){
                        flag = false;
                        break;
                    }
                }
                v_last_index --;
                if(list.size()>=size){
                    break;
                }
                // 再算最后一行
                for(int i=v_last_index;i>=v_first_index;i--) {
                    list.push_back(matrix[h_last_index][i]);
                    if(list.size() >= size){
                        flag = false;
                        break;
                    }
                }
                h_last_index --;
                if(list.size()>=size){
                    break;
                }
                // 最后算开始第一列
                for(int i = h_last_index;i >= h_first_index;i--) {
                    list.push_back(matrix[i][v_first_index]);
                    if(list.size() >= size){
                        flag = false;
                        break;
                    }
                }
                v_first_index ++;
                if(list.size() >= size){
                    break;
                }
            }
            return list;
        }
    };

另外，我还写了一个递归的版本可以用一个bool数组来判断是否遍历，这个消耗一点空间，但是代码看起来很清晰，代码：

int di[4][2] = {
       {0,1},{1,0},{0,-1},{-1,0}};
    vector<int> res;
    vector<vector<bool>> used;
    bool isArea(int x, int y, int row, int col){
        return row>=0 && row<x && col>=0 && col<y;
    }
    void dfs(int d, const vector<vector<int> > &matrix, int x, int y, int row, int col){
        
        int dx = di[d%4][0], dy = di[d%4][1];
        if(isArea(x,y,row,col) && !used[row][col]){
            int tempRow = row, tempCol = col;
            row += dx, col += dy;
            if(!isArea(x,y,row,col) || used[row][col] ){
                if(res.size() + 1 == x * y){//只有最后一个元素了，直接添加并返回
                    res.push_back(matrix[tempRow][tempCol]);
                    return;
                }
                dfs(d + 1, matrix, x, y, row - dx, col - dy);
            }else{
                cout<<matrix[tempRow][tempCol]<<endl;
                res.push_back(matrix[tempRow][tempCol]);
                used[tempRow][tempCol] = true;
                dfs(d, matrix, x, y, row, col); 
            }
        }
        
    }
    vector<int> printMatrix(vector<vector<int> > &matrix) {
        if(!matrix.size() || !matrix[0].size()) return res;
        int x = matrix.size(),y = matrix[0].size();
        
        used = vector<vector<bool>>(x, vector<bool>(y, false));
        dfs(0, matrix, x, y, 0, 0);
        return res;
    }

也可以参考[yxc大神][yxc]的方法。

class Solution {
    public:
        vector<int> printMatrix(vector<vector<int>>& matrix) {
            vector<int> res;
            if (matrix.empty()) return res;
            int n = matrix.size(), m = matrix[0].size();
            vector<vector<bool>> st(n, vector<bool>(m, false));
            int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
            int x = 0, y = 0, d = 1;
            for (int k = 0; k < n * m; k ++ )
            {
                res.push_back(matrix[x][y]);
                st[x][y] = true;
    
                int a = x + dx[d], b = y + dy[d];
                if (a < 0 || a >= n || b < 0 || b >= m || st[a][b])
                {
                    d = (d + 1) % 4;
                    a = x + dx[d], b = y + dy[d];
                }
                x = a, y = b;
            }
            return res;
        }
    };
    
    
    参考链接：https://www.acwing.com/solution/AcWing/content/748/

### 20 包含min函数的栈 ###

定义栈的数据结构，请在该类型中实现一个能够**得到栈中所含最小元素的min函数（时间复杂度应为O（1））**。

class Solution {
    public:
        /**
        我们除了维护基本的栈结构之外，还需要维护一个单调栈，来实现返回最小值的操作。
        下面介绍如何维护单调栈：
    
        当我们向栈中压入一个数时，如果该数 ≤≤ 单调栈的栈顶元素，则将该数同时压入单调栈中；否则，不压入，这是由于栈具有先进后出性质，所以在该数被弹出之前，栈中一直存在一个数比该数小，所以该数一定不会被当做最小数输出。
        当我们从栈中弹出一个数时，如果该数等于单调栈的栈顶元素，则同时将单调栈的栈顶元素弹出。
        单调栈由于其具有单调性，所以它的栈顶元素，就是当前栈中的最小数。
        
        时间复杂度
        四种操作都只有常数次入栈出栈操作，所以时间复杂度都是 O(1)O(1).
        参考链接：https://www.acwing.com/solution/AcWing/content/749/
        */
        stack<int> m;
        stack<int> s;
        void push(int value) {
            s.push(value);
            if(m.empty() || m.top() >= value)
                m.push(value);
        }
        void pop() {
            if(m.top() == s.top()) m.pop();
            s.pop();
        }
        int top() {
            return s.top();
        }
        int min() {
            return m.top();
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70]: /images/20211213/4c141618e7ce40a1be48318d89072809.png
[yxc]: https://www.acwing.com/solution/AcWing/content/748/