239. 滑动窗口最大值
优先队列(最大堆)
class Solution { public: vector<int> maxSlidingWindow(vector<int> &nums, int k) { int n = nums.size(); priority_queue<pair<int, int>> q; for (int i = 0; i < k; i++) { q.emplace(nums[i], i); } vector<int> ans = {q.top().first}; for (int i = k; i < n; i++) { q.emplace(nums[i], i); while (q.top().second <= i - k) { q.pop(); } ans.push_back(q.top().first); } return ans; } };
用最大堆写的最大问题就是不知道何时将最大值弹出，因为是滑动窗口，所以你堆中的最大值可能不在窗口中。该解法的巧妙之处就在于使用pair<int, int>存储元素值与下标。然后在每次滑动窗口返回最大值前，先通过判断最大值下标是否在滑动窗口中，不在的都先剔除。解法十分优美！
单调队列
deque
#include <deque> int main() { deque<int> q; for (int i = 0; i < 5; i++) { q.push_back(i); } for (int it : q) { cout << it << " "; } q.pop_back(); cout << endl; for (int it : q) { cout << it << " "; } cout<<endl; q.push_front(1000); for (int it : q) { cout << it << " "; } cout<<endl; q.pop_front(); for (int it : q) { cout << it << " "; } cout<<endl; system("pause"); return 0; } /* 0 1 2 3 4 0 1 2 3 1000 0 1 2 3 0 1 2 3 */
优势在于有pop_front和push_front，可以对队首元素进行方便的操作。
想法
如果当前的滑动窗口中有两个下标i和j，其中i在j的左侧（i<j），并且i对应的元素不大于j对应的元素,那么只要i在窗口中，nums[i]一定不会是最大值，可以移除。
class Solution { public: vector<int> maxSlidingWindow(vector<int> &nums, int k) { int n = nums.size(); deque<int> q; for (int i = 0; i < k; i++) { while (!q.empty() && nums[i] >= nums[q.back()]) { q.pop_back(); } q.push_back(i); } vector<int> ans = {nums[q.front()]}; for (int i = k; i < n; i++) { while (!q.empty() && nums[i] >= nums[q.back()]) { q.pop_back(); } q.push_back(i); while (q.front() <= i - k) { q.pop_front(); } ans.push_back(nums[q.front()]); } return ans; } };
分块+预处理
class Solution { public: vector<int> maxSlidingWindow(vector<int> &nums, int k) { int n = nums.size(); vector<int> LeftMax(n); vector<int> RightMax(n); int Max; // 该数到左边界的最大值 for (int i = 0; i < n; i++) { if (i % k == 0) { Max = INT_MIN; } Max = max(Max, nums[i]); LeftMax[i] = max(Max, nums[i]); } // 该数到右边界的最大值 Max = INT_MIN; for (int i = n - 1; i >= 0; i--) { if ((i + 1) % k == 0) { Max = INT_MIN; } Max = max(Max, nums[i]); RightMax[i] = max(Max, nums[i]); } vector<int> ans; for (int i = 0; i < n - k + 1; i++) { int j = i + k - 1; ans.push_back(max(RightMax[i], LeftMax[j])); } return ans; } }; nums = [1,3,-1,-3,5,3,6,7], and k = 3
nums = [1,3,-1,-3,5,3,6,7], and k = 3 | 1 3 -1 | -5 4 3 | 5 7 | 如果我们要求 result[1]，也就是下边 i 到 j 范围内的数字的最大值 | 1 3 -1 | -5 4 3 | 5 7 | ^ ^ i j i 到 j 范围内的数字被分割线分成了两部分 我们需要求的其实就是i到右边界的最大值和j到左边界的最大值相比较得到的最大值。
时间复杂度：O(n)
