代码随想录算法训练营第十一天 | 150. 逆波兰表达式求值、 239. 滑动窗口最大值、347.前 K 个高频元素

150. 逆波兰表达式求值

题目：. - 力扣（LeetCode）

思路：遇到数字进栈，遇到符号出栈运算。

代码：

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
    stack<long long> sta;
    for(string s:tokens){
        if(s=="+"||s=="-"||s=="*"||s=="/"){
            long long a1=sta.top();
            sta.pop();
            long long a2=sta.top();
            sta.pop();
            if(s=="+") sta.push(a1+a2);
            else if(s=="-") sta.push(a2-a1);
            else if(s=="*") sta.push(a1*a2);
            else sta.push(a2/a1);
        }
        else
        sta.push(stoll(s));
    }
    int res=sta.top();
    return res;
    }
};

239. 滑动窗口最大值

题目：. - 力扣（LeetCode）

思路：以双向队列为基础容器，元素进队列时将前面更小的元素出队，出队时诺为队头最大元素则出队，否则不做处理，将最大元素始终放在队头。

代码：

class Solution {
public:
    class MyQueue{
        public:
        deque<int> dq;
    void pop(int val){
        if(!dq.empty()&&dq.front()==val)
        dq.pop_front();
    }
    void push(int val){
        while(!dq.empty()&&val>dq.back()){
        dq.pop_back();
        }
        dq.push_back(val);
    }
    int getMax(){ 
      return dq.front();
    }
    };
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        MyQueue que;
        vector<int> res;
        for(int i=0;i<k;i++){
            que.push(nums[i]);
        }
        res.push_back(que.getMax());
    for(int i=0;i<nums.size()-k;++i){
        que.pop(nums[i]);
        que.push(nums[i+k]);
        res.push_back(que.getMax());
    }
    return res;
    }
};

347.前 K 个高频元素

题目：. - 力扣（LeetCode）

思路：使用哈希表统计频率和优先队列自定义比较函数实现小顶堆。

代码：

class Solution {
public:
    // 小顶堆
    class mycomparison {
    public:
        bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
            return lhs.second > rhs.second;
        }
    };
    vector<int> topKFrequent(vector<int>& nums, int k) {
        // 要统计元素出现频率
        unordered_map<int, int> map; // map<nums[i],对应出现的次数>
        for (int i = 0; i < nums.size(); i++) {
            map[nums[i]]++;
        }

        // 对频率排序
        // 定义一个小顶堆，大小为k
        priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;

        // 用固定大小为k的小顶堆，扫面所有频率的数值
        for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {
            pri_que.push(*it);
            if (pri_que.size() > k) { // 如果堆的大小大于了K，则队列弹出，保证堆的大小一直为k
                pri_que.pop();
            }
        }

        // 找出前K个高频元素，因为小顶堆先弹出的是最小的，所以倒序来输出到数组
        vector<int> result(k);
        for (int i = k - 1; i >= 0; i--) {
            result[i] = pri_que.top().first;
            pri_que.pop();
        }
        return result;

    }
};