力扣 滑动窗口最大值

滑动窗口最大值

题目描述

题目分析

维护一个定长窗口的最大值，每当窗口滑动时都有一个新的元素进入和一个原有的元素脱离。
比力简朴的方法就是用一个优先队列维护窗口最大值
但是堆的盘算成本时最坏时是                                   O                         (                         n                         log                         ⁡                         n                         )                              O(n\log n)                  O(nlogn)
优化：

单调队列
相比于堆，堆生存了全部元素，导致维护的成本较高，而单调队列是在保持次序的情况下只生存符合单调性的元素，不需要重新重新调整结构，换句话说盘算的复杂度最坏时为                                   O                         (                         n                         )                              O(n)                  O(n)
分块预处理
将全部元素按滑动窗口的大小分块，我们可以得到                                   [                         n                         /                         k                         ]                         +                         1                              [n/k] + 1                  [n/k]+1个块
为了方便的得到块内最大值，我们可以参考前缀和的方式盘算块内的前缀最大值，取                                   i                              i                  i 为                                   k                              k                  k的倍数时就可以取得第                                   i                         /                         k                              i/k                  i/k块的最大值
问题在于，滑动窗口不愿定就是我们分好的块
所以考虑特别情况，滑动窗口为                                   [                         i                         ,                         j                         ]                              [i,j]                  [i,j]，设                                   m                         ∈                         [                         i                         ,                         j                         ]                         且                         k                         ∣                         m                              m \in [i,j] 且 k\mid m                  m∈[i,j]且k∣m(整除)
则                                   p                         r                         e                         m                         a                         x                         [                         j                         ]                              premax[j]                  premax[j]表示了                                   m                         a                         x                         (                         n                         u                         m                         s                         [                         m                         :                         j                         ]                         )                              max(nums[m:j])                  max(nums[m:j])
如今问题转为了怎么求                                   m                         a                         x                         (                         n                         u                         m                         s                         [                         i                         :                         m                         )                         )                              max(nums[i:m))                  max(nums[i:m))
我们希望用                                   i                              i                  i表示这一段的最大值。注意到                                   i                         :                         m                              i:m                  i:m是一种后缀形式，相应的我们可考虑块内的后缀最大值
界说                                   s                         u                         f                         m                         a                         x                         [                         i                         ]                         表示了                         m                         a                         x                         (                         n                         u                         m                         s                         [                         i                         :                         m                         )                         )                              sufmax表示了max(nums[i:m))                  sufmax表示了max(nums[i:m))
解决问题

1.优先队列

1. class Solution {
2. public:
3.     vector<int> maxSlidingWindow(vector<int>& nums, int k) {
4.         int n = nums.size();
5.         priority_queue<pair<int, int>> q;
6.         for (int i = 0; i < k; ++i) {
7.             q.emplace(nums[i], i);
8.         }
9.         vector<int> ans = {q.top().first};
10.         for (int i = k; i < n; ++i) {
11.             q.emplace(nums[i], i);
12.             while (q.top().second <= i - k) {
13.                 q.pop();
14.             }
15.             ans.push_back(q.top().first);
16.         }
17.         return ans;
18.     }
19. };

复制代码

2.单调队列

1. class Solution {
2. public:
3.     vector<int> maxSlidingWindow(vector<int>& nums, int k) {
4.         int n = nums.size();
5.         deque<int> q;
6.         for(int i = 0; i < k; ++i){
7.             while(!q.empty() && nums[i] >= nums[q.back()]){
8.                 q.pop_back();
9.             }
10.             q.push_back(i);
11.         }
12.         vector<int> ans = {nums[q.front()]};
13.         for(int i = k; i < n; ++i){
14.             while(!q.empty() && nums[i] >= nums[q.back()]){
15.                 q.pop_back();
16.             }
17.             q.push_back(i);
18.             while(q.front() <= i - k){
19.                 q.pop_front();
20.             }
21.             ans.push_back(nums[q.front()]);
22.         }
23.         return ans;
24.     }
25. };

复制代码

3.分块预处理

1. class Solution {
2. public:
3.     vector<int> maxSlidingWindow(vector<int>& nums, int k) {
4.         int n = nums.size();
5.         vector<int> prefixMax(n), suffixMax(n);
6.         for (int i = 0; i < n; ++i) {
7.             if (i % k == 0) {
8.                 prefixMax[i] = nums[i];
9.             }
10.             else {
11.                 prefixMax[i] = max(prefixMax[i - 1], nums[i]);
12.             }
13.         }
14.         for (int i = n - 1; i >= 0; --i) {
15.             if (i == n - 1 || (i + 1) % k == 0) {
16.                 suffixMax[i] = nums[i];
17.             }
18.             else {
19.                 suffixMax[i] = max(suffixMax[i + 1], nums[i]);
20.             }
21.         }
23.         vector<int> ans;
24.         for (int i = 0; i <= n - k; ++i) {
25.             ans.push_back(max(suffixMax[i], prefixMax[i + k - 1]));
26.         }
27.         return ans;
28.     }
29. };

复制代码

总结

优先队列，单调队列，动态维护最值
分块预处理，空间换时间，从团体出发，问题分治，对称性思想

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。