代码随想录day11 150. 逆波兰表达式求值 、 239. 滑动窗口最大值 、 347.前 K 个高频元素

代码随想录day11 150. 逆波兰表达式求值 、 239. 滑动窗口最大值 、 347.前 K 个高频元素

150. 逆波兰表达式求值

栈的应用 学数据结构时候写过，注意要使用long long

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<long long> st;
        for (int i = 0; i < tokens.size(); i++) {
            if (tokens[i] == "+" || tokens[i] == "-"
                || tokens[i] == "*" || tokens[i] == "/") {
                    long long right = st.top();
                    st.pop();
                    long long left = st.top();
                    st.pop();
                    if (tokens[i] == "+") st.push(left + right);
                    if (tokens[i] == "-") st.push(left - right);
                    if (tokens[i] == "*") st.push(left * right);
                    if (tokens[i] == "/") st.push(left / right);
                } else {
                    st.push(stoll(tokens[i]));
                }
        }
        return st.top();
    }
};

239. 滑动窗口最大值

这题是看卡哥视频的，但我不是很习惯pop的写法，因为我觉得pop就是单纯的弹出元素，而这里实际涉及了外界的下标，因为左下标-1元素值等于首元素，所以才觉得要弹出元素，属于和外界逻辑相关，而不是和队列本意相关，所以我就放到了函数体内，然后单调队列，其实就是对deque的入队作了限制，入队元素如果大于尾元素，则要不断弹出

class Solution {
public:

    void push(deque<int> &que, int val) {
        while (!que.empty() && val > que.back()) {
            que.pop_back();
        }
        que.push_back(val);
    }

    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> que;
        vector<int> res;
        for (int i = 0; i < k; i++) {
            push(que, nums[i]);
        }
        res.push_back(que.front());
        for (int i = k; i < nums.size(); i++) {
            if (!que.empty() && que.front() == nums[i - k]) {
                que.pop_front();
            }
            push(que, nums[i]);
            res.push_back(que.front());
        }
        return res;
    }
};

347. 前 K 个高频元素

想法和卡哥差不多都是用map统计然后放入优先队列进行排序，但我本来想的是用大顶堆，最后弹出两个频率最大的元素，但后来发现这复杂度是O(nlogn)，所以不符合要求

几个注意的点是priority_que的模板参数 第一个是元素类型，第二个是容器类型，第三个类(重写了仿函数，或者如果元素是自定义类可以重写operator大小比较)，第三个参数得是类，我写lamda直接报错了

一个小诀窍就是vector可以正序或者倒叙写入就可以把实现想要的顺序

class Solution {
public:
    struct cmp {
        bool operator()(const pair<int,int> &p1,const pair<int,int> &p2) {
            return p1.second > p2.second;
        }
    };


    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> countMap;
        for (auto &ele : nums) {
            countMap[ele]++;
        }
        priority_queue<pair<int,int>,vector<pair<int,int>>,cmp> priQue;
        for (auto &ele : countMap) {
            priQue.push(ele);
            if (priQue.size() > k) {
                priQue.pop();
            }
        }
        vector<int> res(k);
        for (int i = k - 1; i >= 0; i--) {
            res[i] = priQue.top().first;
            priQue.pop();
        }
        return res;
    }
};