day11 栈与队列2

150. 逆波兰表达式求值

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        int num1, num2, res;
        for (string s: tokens) {
            if (s != "+" && s != "-" && s != "*" && s != "/") {
                st.push(stoi(s));
                continue;
            }
            num2 = st.top();
            st.pop();
            num1 = st.top();
            st.pop();
            if (s == "+") {
                res = num1 + num2;
            }
            else if (s == "-") {
                res = num1 - num2;
            }
            else if (s == "*") {
                res = num1 * num2;
            }
            else {
                res = num1 / num2;
            }
            st.push(res);
        }
        return st.top();
    }
};

239. 滑动窗口最大值

class Solution {
public:
    void addToHeap(deque<pair<int, int>> &deq, int num, int index) {
        if (deq.empty() || deq.back().first >= num) {
            deq.push_back(pair<int, int>(num, index));
        }
        else {
            while (!deq.empty() && deq.back().first < num) {
                deq.pop_back();
            }
            deq.push_back(pair<int, int>(num, index));
        }
    }

    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        deque<pair<int, int>> deq;
        for (int i = 0; i < k; i ++) {
            addToHeap(deq, nums[i], i);
        }
        res.push_back(deq.front().first);
        for (int i = k; i < nums.size(); i ++) {
            addToHeap(deq, nums[i], i);
            if (deq.front().second <= i - k) {
                deq.pop_front();
            }
            res.push_back(deq.front().first);
        }
        return res;
    }
};

347.前 K 个高频元素

class Solution {
private:
    static bool cmp(const pair<int, int> &a, const pair<int, int> &b) {
        return a.second > b.second;
    }

public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        if (k == nums.size()) {
            return nums;
        }
        vector<int> res;
        unordered_map<int, int> umap;
        for (int num: nums) {
            umap[num] ++;
        }
        vector<pair<int, int>> vec(umap.begin(), umap.end());
        sort(vec.begin(), vec.end(), cmp);
        for (int i = 0; i < k; i ++) {
            res.push_back(vec[i].first);
        }
        return res;
    }
};