题解 | #最大体重的牛#

考察知识点： 栈

题目分析：

 本题中的难点在于怎样用常数时间找到栈中的最大值。可以使用一个额外的栈来保存每一层栈中的最大值。即：

 保存体重的栈和保存每一层最大值的栈共用同一个指针，当弹出栈顶元素时，最大栈也会弹出栈顶元素。这样维护好每一层的最大值，当弹出栈顶元素时就不必重新计算栈中的最大值了。

所用编程语言： C++

class MaxCowStack {
public:
    void push(int id, int weight) {
        stk[tt] = weight;
        // Max = Max >= weight ? Max : weight;
        maxStk[tt] = getMax() >= weight ? getMax() : weight;
        tt++;
        // pq.push(weight);
    }
    int pop() {
        int topVal = top();
        tt--;
        return topVal;
    }
    int top() {
        return stk[tt - 1];
    }
    int getMax() {
        return maxStk[tt - 1];
    }
private:
    int Max = -1;
    int tt = 0;
    std::array<int, 30010> stk;
    std::array<int, 30010> maxStk;
    //priority_queue<int> pq;
};
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param op string字符串vector 
     * @param vals int整型vector<vector<>> 
     * @return int整型vector
     */
    vector<int> max_weight_cow(vector<string>& op, vector<vector<int> >& vals) {
        // write code here
        int size = op.size();
        MaxCowStack stk;
        vector<int> res;
        int start = 0;
        while(start < size - 1 && op[start] != "MaxCowStack") {
            res.push_back(-1);
            start++;
        }
        if (op[start] != "MaxCowStack") return res;
        for (int i = start; i < size; i++) {
            string opstr = op[i];
            vector<int> val = vals[i];
            if (opstr == "MaxCowStack") res.push_back(-1);
            if (opstr == "push") {
                stk.push(val[0], val[1]);
                res.push_back(-1);
            }
            if (opstr == "pop") {
                stk.pop();
                res.push_back(-1);
            }
            if (opstr == "getMax") res.push_back(stk.getMax());
            if (opstr == "top") res.push_back(stk.top());
        }
        return res;
    }
};