LeetCode HOT100 - 滑动窗口最大值

滑动窗口移动的过程就是不断有元素进/出的过程

要维护这个过程中现有元素的最大值

那最基础的就是维护一个元素有没有出现

但是一个窗口中可能有多个相同元素，因此再加上元素的出现次数

因此一个数组来维护出现次数，一个优先队列来维护现有元素

每次移动同步对元素进行更新维护

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& a, int k) {unordered_map<int, int> cnt;priority_queue<int, vector<int>> pq;for (int i = 0; i < k; i++) {cnt[a[i]]++;if (cnt[a[i]] == 1) {pq.push(a[i]);}}int n = a.size();vector<int> ans;ans.emplace_back(pq.top());for (int l = 0, r = k; r < n; l++, r++) {cnt[a[l]]--;cnt[a[r]]++;if (cnt[a[r]] == 1) {pq.emplace(a[r]);}while (!pq.empty() && cnt[pq.top()] == 0) {pq.pop();}ans.emplace_back(pq.top());}return ans;}
};