Leetcode 239-滑動窗口最大值

題目描述

https://leetcode.cn/problems/sliding-window-maximum/description/

解題思路

在本題中我們使用自定義的單調隊列來實現：

pop：如果窗口移除的元素 value 等于單調隊列的出口元素，那么隊列彈出元素，否則不進行任何操作

push：如果 push 的元素 value 大于入口元素的數值，那么就將隊列入口的元素彈出，直到 push 元素的數值小于隊列入口元素的數值為止

返回當前窗口的最大值：調用 que.front()

class Solution {
private:class MyQueue {public:deque<int> que; //使用deque實現單調隊列void pop(int value) {if (!que.empty() && value == que.front()) {que.pop_front();}}void push(int value) {while (!que.empty() && value > que.back()) {que.pop_back();}que.push_back(value);}int front() {return que.front();}};
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {MyQueue que;vector<int> result;for (int i = 0; i < k; i++) {que.push(nums[i]);}result.push_back(que.front());for (int i = k; i < nums.size(); i++) {que.pop(nums[i - k]);que.push(nums[i]);result.push_back(que.front());}return result;}
};

Leetcode 347-前 K 個高頻元素

題目描述

https://leetcode.cn/problems/top-k-frequent-elements/description/

解題思路

這道題目需要解決三個部分的問題：

1. 統計元素的出現頻率：
我們可以使用 unordered_map 來解決，其中 key 表示元素的值，value 表示值出現的次數
2. 對頻率進行排序：
使用優先級隊列，其是一個披著隊列外衣的堆。優先級隊列對外接口是從隊頭取元素，從隊尾添加元素，其內部的元素自動依照元素的權值排列。優先級隊列缺省情況下 priority_queue 利用 max-heap 大頂堆完成對元素的排列，大頂堆是以 vector 為表現形式的完全二叉樹。

堆是完全二叉樹，樹中的每個結點都不小于（或不大于）其左右孩子的值。父親結點大于等于左右孩子的是大頂堆，小于等于左右孩子的是小頂堆。

選用優先級隊列而不是快排：我們只需要報告前 K 個高頻元素而不是全部元素，因此只需要維護 K 個有序序列即可，當 n 非常大時，這樣的方法可以降低時間復雜度。

使用小頂堆而不是大頂堆：因為要統計最大前 K 個元素，如果選用大頂堆會將最大的元素彈出不符合要求，而使用小頂堆可以每次將最小的元素彈出，最后小頂堆中積累的才是前 K 個最大元素。

3. 找出前 K 個高頻元素

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;for (int i = 0; i < nums.size(); i++) {map[nums[i]]++;}//根據頻率進行排序//定義一個小頂堆，大小為kpriority_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，則從隊列彈出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;}};

棧與隊列總結

棧和隊列是容器適配器，底層容器使用不同的容器，那么棧內數據在內存中的分布就不一定連續。
在缺省狀況下，棧和隊列的默認底層容器時 deque，其內存分布不連續。

遞歸的實現是棧：每一次遞歸調用都會把函數的局部變量、參數值和返回地址等壓入調用棧中，然后遞歸返回的時候，從棧頂彈出上一次遞歸的各項參數，所以這就是遞歸為什么可以返回上一層位置的原因。