熊二 | C++ | #最大体重的牛#

题目考察的知识点

• 辅助栈

题目解答方法的文字分析

借用一个辅助栈 min_stack，用于存获取 stack 中最小值。

算法流程：

push() 方法： 每当push()新值进来时，如果 小于等于 min_stack 栈顶值，则一起 push() 到 min_stack，即更新了栈顶最小值；

pop() 方法： 判断将 pop() 出去的元素值是否是 min_stack 栈顶元素值（即最小值），如果是则将 min_stack 栈顶元素一起 pop()，这样可以保证 min_stack 栈顶元素始终是 stack 中的最小值。

getMin()方法： 返回 min_stack 栈顶即可。

min_stack 作用分析：

min_stack 等价于遍历 stack所有元素，把升序的数字都删除掉，留下一个从栈底到栈顶降序的栈。

相当于给 stack 中的降序元素做了标记，每当 pop() 这些降序元素，min_stack 会将相应的栈顶元素 pop() 出去，保证其栈顶元素始终是 stack 中的最小元素。

复杂度分析：

时间复杂度 O(1) ：压栈，出栈，获取最小值的时间复杂度都为 O(1) 。

空间复杂度 O(N) ：包含 N 个元素辅助栈占用线性大小的额外空间。

本题解析所用的编程语言

• cpp

完整且正确的编程代码

class Solution {
public:
    vector<int> max_weight_cow(vector<string>& op, vector<vector<int>>& vals) {
        stack<int> stk, stk_max;
        vector<int> res;
        int n = (int)op.size();

        for (int i = 0; i < n; i++) {
            auto& s = op[i];
            if (s == "push") {
                int id=vals[i][0], w=vals[i][1];
                
                stk.push(w);
                if (!stk_max.empty())
                    stk_max.push(max(stk_max.top(), w));
                else
                    stk_max.push(w);

                res.push_back(-1);
            } else if (s == "pop") {
                stk.pop();
                stk_max.pop();
                res.push_back(-1);
            } else if (s == "top") {
                // cout <<"stk_max.size(): "<< stk_max.size() <<endl;
                if(stk_max.empty())res.push_back(-1);
                else {
                    res.push_back(stk.top());
                }
            } else if (s == "getMax") {
                if(stk_max.empty())res.push_back(-1);
                else res.push_back(stk_max.top());
            }else{
                res.push_back(-1);
            }
            // cout << res.back()<< endl;
        }
        return res;
    }
};
/*
2023年8月8日，min栈变形，自己，5min
*/

EOF