题解 | #最大体重的牛#

大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

这道题目考察了设计一个数据结构，其中涉及栈的使用，要求在常数时间内支持插入、删除和查询操作，并且能够高效地获取最大权值的牛的体重。

题目解答方法的文字分析

在这个题目中，我们需要实现一个支持 push、pop、top 和 getMax 操作的数据结构。我们可以利用栈来实现这个数据结构，同时使用一个辅助栈来记录当前栈中的最大权值。

• push 操作：将牛的编号和体重压入牛栈中，如果体重大于等于最大权值栈的栈顶元素，就将该体重压入最大权值栈中。
• pop 操作：从牛栈和最大权值栈中分别弹出栈顶元素，但仅当牛栈的栈顶元素体重等于最大权值栈的栈顶元素体重时，才将最大权值栈的栈顶元素弹出。
• top 操作：返回牛栈的栈顶元素的体重。
• getMax 操作：返回最大权值栈的栈顶元素，即当前栈中的最大权值。

本题解析所用的编程语言

本题解析所用的编程语言是 C++。

完整且正确的编程代码

class MaxCowStack {
private:
    stack<pair<int, int>> cowStack;  // 用来存储牛的编号和体重
    stack<int> maxWeightStack;       // 用来存储当前栈中的最大权值

public:
    MaxCowStack() {
        // 初始化
    }

    void push(int id, int weight) {
        cowStack.push(make_pair(id, weight));
        if (maxWeightStack.empty() || weight >= maxWeightStack.top()) {
            maxWeightStack.push(weight);
        }
    }

    void pop() {
        if (!cowStack.empty()) {
            if (cowStack.top().second == maxWeightStack.top()) {
                maxWeightStack.pop();
            }
            cowStack.pop();
        }
    }

    int top() {
        return cowStack.top().second;
    }

    int getMax() {
        return maxWeightStack.top();
    }
};
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) {
    MaxCowStack maxCowStack;
    vector<int> result;

    for (int i = 0; i < op.size(); ++i) {
        if (op[i] == "push") {
            maxCowStack.push(vals[i][0], vals[i][1]);
            result.push_back(-1);
        } else if (op[i] == "pop") {
            maxCowStack.pop();
            result.push_back(-1);
        } else if (op[i] == "top") {
            result.push_back(maxCowStack.top());
        } else if (op[i] == "getMax") {
            result.push_back(maxCowStack.getMax());
        }else{
            result.push_back(-1);
        }
    }

    return result;
}
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！