脚本宝典收集整理的这篇文章主要介绍了滑动窗口，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
【题目描述】
给定一个大小为 @H_304_6@n≤106 的数组。
有一个大小为 k 的滑动窗口，它从数组的最左边移动到最右边。
你只能在窗口中看到 k 个数字。
每次滑动窗口向右移动一个位置。
以下是一个例子：
该数组为 [1 3 -1 -3 5 3 6 7]，k 为 3。
| 窗口位置 | 最小值 | 最大值 |
|---|---|---|
| [1 3 -1] -3 5 3 6 7 | -1 | 3 |
| 1 [3 -1 -3] 5 3 6 7 | -3 | 3 |
| 1 3 [-1 -3 5] 3 6 7 | -3 | 5 |
| 1 3 -1 [-3 5 3] 6 7 | -3 | 5 |
| 1 3 -1 -3 [5 3 6] 7 | 3 | 6 |
| 1 3 -1 -3 5 [3 6 7] | 3 | 7 |
你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。
输入包含两行。
第一行包含两个整数 n 和 k，分别代表数组长度和滑动窗口的长度。
第二行有 n 个整数，代表数组的具体数值。
同行数据之间用空格隔开。
输出包含两个。
第一行输出，从左至右，每个位置滑动窗口中的最小值。
第二行输出，从左至右，每个位置滑动窗口中的最大值。
8 3
1 3 -1 -3 5 3 6 7
-1 -3 -3 -3 3 3
3 3 5 5 6 7
使用单调队列（存储数据对应的下标）保持当前窗口中的最大值即可（最大值举例）：
①如果当前进入窗口的数字num比窗口末尾元素x要大，就不断将窗口末尾元素x出队，直到num < x，或者是队空，并将num的下标入队。需要注意的是如果遇到相等的情况，即num == x，x也需要出队，因为num的下标比x更新。
②如果当前队头元素下标pos已经滑出滑动窗口了，那么就需要将其从队头出队，判断的依据就是比较pos与窗口末端滑到的位置i，如果pos < i - k + 1，就说明pos已经滑出窗口了，需要出队。
1 #include <iostream> 2 #include <deque> 3 #include <algorIThm> 4 using namespace std; 5 tyPEdef long long LL; 6 int N,K; 7 LL num[1000009]; 8 int main() 9 { 10 cin >> N >> K; 11 for(int i = 1;i <= N;++i) 12 { 13 cin >> num[i]; 14 } 15 deque<LL> que; 16 for(int i = 1;i <= N;++i) 17 { 18 while(!que.empty() && que.front() < (i-K+1)) 19 { 20 que.pop_front(); 21 } 22 while(!que.empty() && num[que.back()] >= num[i]) 23 { 24 que.pop_back(); 25 } 26 que.push_back(i); 27 if(i >= K) 28 cout << num[que.front()] << " "; 29 } 30 cout << endl; 31 while(!que.empty()) 32 { 33 que.pop_back(); 34 } 35 for(int i = 1;i <= N;++i) 36 { 37 while(!que.empty() && que.front() < (i-K+1)) 38 { 39 que.pop_front(); 40 } 41 while(!que.empty() && num[que.back()] <= num[i]) 42 { 43 que.pop_back(); 44 } 45 que.push_back(i); 46 if(i >= K) 47 cout << num[que.front()] << " "; 48 } 49 return 0; 50 }
以上是脚本宝典为你收集整理的滑动窗口全部内容，希望文章能够帮你解决滑动窗口所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。