Day11| 150.逆波兰表达式求值、239.滑动窗口最大值、347.前 K个高频元素、栈与队列总结

2025-07-19

代码随想录

150.逆波兰表达式求值

题目链接：150.逆波兰表达式求值
文档讲解：代码随想录
状态：思路简单，细节出错

思路

逆波兰式（Reverse Polish Notation，RPN，或逆波兰记法），也叫后缀表达式（将运算符写在操作数之后），常用于计算机内部。

类似消消乐问题，使用栈

本题细节：string类型auto遍历，i为string类型，比较时注意使用双引号如i == "+"

学习了string转为int、long、long long的函数stoi、stol、stoll

模拟过程：

chart

题解

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        int first = 0, second = 0;
        for(auto i : tokens)
        {
            
            //if(i == '+' || i == '-' || i == '*' || i == '/')
            if(i == "+" || i == "-" || i == "*" || i == "/")
            {
                second = st.top();st.pop();
                first = st.top();st.pop();
                //注意顺序，栈底在前顶在后
                if(i == "+")st.push(first+second);
                else if(i == "-")st.push(first-second);
                else if(i == "*")st.push(first*second);
                else if(i == "/")st.push(first/second);
            }
            else st.push(stoi(i));
        }
        return st.top();
    }
};

239.滑动窗口最大值

题目链接：239.滑动窗口最大值
文档讲解：代码随想录
状态：不会，单调队列的应用

思路

深度理解题意：

chart

暴力解法：规定一个k大小窗口，每次向后移位并遍历k取最大值，复杂度O(n×k)。

优化方向：主循环遍历数组不可少，滑动窗口内遍历最大值可以优化。滑动窗口运作的过程类似于队列的入队出队过程，考虑使用队列解决

队列如何取最大呢？1.优先级队列（大/小根堆）2.单调队列。本题对于队列的要求：可取最大值（1、2均满足），若有边缘元素，删除！此时大根堆貌似不能完成任务了，因为堆只能在根节点操作，其他的无法选中啊（堆封装很好，不可操作）。

考虑单调队列（可操作性）：构建单调递增序列->满足队列取最大:如何满足第一个数是最大呢？对入队元素进行逐个比较，若小于入队元素则删除(关键点),这样构建的序列是单调递增的，且严格按照数组下标顺序从队头到队尾，这一性质也完成了每次待移除的元素仅可能出现在队头。

单调队列运作方式：

chart

题解

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

347.前K个高频元素

题目链接：347.前K个高频元素
文档讲解：代码随想录
状态：不会，学习了优先级队列（大、小根堆）

思路

遍历一遍数组，用哈希表（map）存储各个数字以及出现次数必不可少。

本题难点在于如何给map按value值排序，既然没有现成库函数，选择一种排序方式，因为这一章是栈与队列，那必然选优先级队列了（黑幕啊）

那选择大根堆还是小根堆呢？题目要求选择k个最大，常规想法肯定想建立大根堆，建完后堆排序取前k个即可，维护全部n个节点;若选择小根堆，建立n个节点，没法取k个最大，建立k个节点，每次将大的下沉、小的上升弹出，则最后剩下的k个一定为最大。小根堆维护节点少，故选。

chart

补充优先级队列（大、小根堆）用法：

📌定义：堆是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。

📌1. 包含头文件，与队列相同

#include <queue>
//原版模型
template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;

📌2. 创建对象，共有三个参数，后两个可缺省

priority_queue<T, vector<T>, less<T>>;

| 参数 | 说明 | 默认值 | | ————- | ————————————————— | ——————- | | T | 存储的元素类型 | 无 | | Container | 底层容器（必须支持 push_back, pop_back, front, back） | std::vector<T> | | Compare | 比较函数（决定堆是大顶堆还是小顶堆） | std::less<T>（大顶堆） |

📌 3. 创建方式（4种常见方式） ✅ (1) 默认大顶堆

#include <queue>
priority_queue<int> max_heap;  // 等价于 priority_queue<int, vector<int>, less<int>>

✅ (2) 小顶堆（最小堆）

#include <queue>
priority_queue<int, vector<int>, greater<int>> min_heap;

✅ (3) 存储自定义类型

struct Node {
    int val;
    int freq;
};
// 大顶堆（按 freq 降序）
priority_queue<Node, vector<Node>, function<bool(const Node&, const Node&)>> max_heap(
    [](const Node& a, const Node& b) { return a.freq < b.freq; }
);
// 小顶堆（按 freq 升序）
priority_queue<Node, vector<Node>, function<bool(const Node&, const Node&)>> min_heap(
    [](const Node& a, const Node& b) { return a.freq > b.freq; }
);

✅ (4) 使用自定义比较类(重点)

struct Compare {
    bool operator()(const int& a, const int& b) {
        return a > b;  // 小顶堆
    }
};
priority_queue<int, vector<int>, Compare> min_heap2;

题解

class Solution {
public:
    class myfunctor
    {
        public://注意要class默认私有
        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) {
        vector<int> result;
        unordered_map<int, int> umap;
        for(int i = 0;i<nums.size();i++)umap[nums[i]]++;

        priority_queue<pair<int,int>, vector<pair<int,int>>, myfunctor> pri_que;

        for(auto i : umap)
        {
            pri_que.push(i);
            if(pri_que.size()>k)pri_que.pop();
        }

        for(int i = 0;i<k;i++)
        {
            result.push_back(pri_que.top().first);
            pri_que.pop();
        }
        return result;


    }
};

栈与队列总结

知道栈与队列的基本性质，了解他们在C++中并非容器。

📌栈里面的元素在内存中是连续分布的么？

这个问题有两个陷阱：

陷阱1：栈是容器适配器，底层容器使用不同的容器，导致栈内数据在内存中不一定是连续分布的。 陷阱2：缺省情况下，默认底层容器是deque，那么deque在内存中的数据分布是什么样的呢？答案是：不连续的，下文也会提到deque。

要对数据结构深挖基础，了解底层构成以及上层应用。