题解 | #最大体重的牛# STL的使用

知识点

STL的使用 模拟

题意分析

维护一个数据结构, 可以获取栈顶的权值 / 抛出栈顶元素 / 获取最大的元素

一种比较取巧的办法是利用multiset维护权值, 并用栈去模拟

获取最大权值可以使用 *S.rbegin()单次时间复杂度

每次插入 / 删除元素的时间复杂度

时间复杂度

瓶颈在维护multiset , 每次插入 / 删除元素的时间复杂度

总体时间复杂度

AC code (C++)

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
        multiset<int> S;
        stack<int> stk;
        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);
                S.insert(w);
                res.push_back(-1);
            }
            else if (s == "pop") {
                if (!stk.empty()) {
                    S.erase(S.find(stk.top()));
                    stk.pop();
                }
                res.push_back(-1);
            }
            else if (s == "top") {
                if (stk.empty()) {
                    res.push_back(-1);
                }
                else {
                    res.push_back(stk.top());
                }
            }
            else if (s == "getMax") {
                if (stk.empty()) res.push_back(-1);
                else res.push_back(*S.rbegin());
            }
            else {
                // MaxCowStack
                res.push_back(-1);
            }
        }
        return res;
    }
};