LeetCode.347前k个高频元素
思路
（1）统计频次：用unordered_map遍历nums原数组，key存数组元素值，value存该元素出现次数。
（2）维护大小为 k 的小顶堆(为什么选择小顶堆而不是大顶堆如下图)（后边出面试常考的时候在细细说topK问题的时候仔细说这个）
（3）组装result：依次取出堆顶元素的key（nums[i]），倒序填入结果数组返回。
代码
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>mp; for (int i = 0; i < nums.size(); i++) { mp[nums[i]]++; } priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison>pri_que; for (unordered_map<int, int>::iterator it = mp.begin(); it != mp.end(); it++) { pri_que.push(*it); if (pri_que.size() > k) { pri_que.pop(); } } vector<int>result(k); for (int i = k - 1; i >= 0; i--) { result[i] = pri_que.top().first; pri_que.pop(); } return result; } };小结
(1)这个自定义函数是什么？
是一个仿函数（函数对象），用来做比较规则，一般给priority_queue（优先队列 / 大根堆小根堆）用。
这个仿函数的比较规则：拿 pair 的第二个成员比较，用于优先队列，做成按第二个值的大根堆。
(2)仿函数又是什么呢？
仿函数（函数对象）= 重载了()运算符的类，它的对象用起来和普通函数完全一样，所以叫 "模仿函数的东西"。
(3)那它和普通函数有什么区别吗？
仿函数可以在类里存自己的状态 / 成员变量，普通函数做不到；STL 的模板（priority_queue、sort）要求传一个类型，仿函数是类可以直接当模板参数传，普通函数不行。
LeetCode.239.滑动窗口的最大值
思路
（其实懒大王只会暴力求解来着，但是苦哈哈过不去 只得求助豆包之......）
- 用双端队列存元素下标，队列内对应的值从队头到队尾严格递减，队头永远是当前窗口的最大值；
- 每遍历一个新元素做三步：把滑出窗口的队头元素弹出、把队尾所有比当前元素小的元素淘汰、再把新元素下标入队尾；
- 窗口成型后，直接取队头的值就是当前窗口最大值，存入结果即可。
代码
class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { deque<int> dq; // 存元素下标，队列内对应的值从队头到队尾严格递减 vector<int> res; for (int i = 0; i < nums.size(); i++) { // 1. 队头元素已经滑出当前窗口，直接弹出 if (!dq.empty() && dq.front() <= i - k) { dq.pop_front(); } // 2. 队尾所有比当前元素小的，全部弹出： // 后面来了更大的数，这些小的永远没机会当窗口最大值，提前淘汰 while (!dq.empty() && nums[dq.back()] < nums[i]) { dq.pop_back(); } // 3. 当前下标入队尾 dq.push_back(i); // 4. 第一个窗口形成后，队头就是当前窗口最大值，存入结果 if (i >= k - 1) { res.push_back(nums[dq.front()]); } } return res; } };LeetCode94.二叉树的中序遍历（迭代算法）
思路
用两个容器分工：result存最终结果，stack临时存放待回溯的节点指针。
只要还有节点要压、或还有节点要弹，就不停向左压，压到底之后就开始弹栈访问。
代码
class Solution { public: vector<int> inorderTraversal(TreeNode* root) { //用迭代算法实现中序遍历，（左-根-右） //创建一个数组存放最终结果，创建一个栈存放临时的节点 vector<int>result; stack<TreeNode*>sk; TreeNode* cur=root; //如果根为空的话，直接返回空的数组 if(root==nullptr)return result; //根不为空时，一直往左子树“读”，直到叶子节点为止，就开始往外“弹”入结果数组,然后根，右 while(cur!=nullptr||!sk.empty()){ while(cur!=nullptr){ sk.push(cur); cur=cur->left; } TreeNode* node = sk.top(); result.push_back(node->val); sk.pop(); cur=node->right; } return result; } };
