滑动窗口学习
第一次与它遇见是在某一次lc周赛第三题,没写出来,也没补题。后面好像还遇到一次忘记了。
再一次遇到就是昨天学校学长举办的小比赛,前四题基本都是手速过去了,到了第五题,我感觉这题目很熟悉
,但想了很久也没思路。问群里人给点hint,说是滑动窗口。我仔细一想,确实不会,就没打了。
滑动窗口不会的最大原因是,白皮书上确实是没有这个知识点的,我也不知道为什么。
总之,今天花点时间,补下基础。
ACW 滑动窗口例题
首先呢,就是最简单的办法,模拟题目的意思。
也很简单的TLE了。不过写一写,总归是好的。省时间,没用数组模拟。反正总归过不了。
#include <iostream>
#include <queue>
using namespace std;
const int N = 1e6 + 10;
int a[N];
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,k;
cin >> n >> k;
for(int i = 0;i<n;i++) cin >> a[i];
queue<int> q;
int i = 0;
for(;i<k-1;i++){
q.push(a[i]);
}
for(;i<n;i++){
q.push(a[i]);
int min_v = 1 << 30;
for(int j = 0;j<k;j++){
min_v = min(min_v,q.front());
q.push(q.front());
q.pop();
}
q.pop();
cout << min_v <<" ";
}
cout << endl;
q = queue<int>();
i = 0;
for(;i<k-1;i++){
q.push(a[i]);
}
for(;i<n;i++){
q.push(a[i]);
int min_v = -1 << 30;
for(int j = 0;j<k;j++){
min_v = max(min_v,q.front());
q.push(q.front());
q.pop();
}
q.pop();
cout << min_v <<" ";
}
cout << endl;
return 0;
}
所谓滑动窗口,就是对这个队列的优化,我们并不需要,每次需要最小值的时候都遍历一遍这个队列,我们可以在进行一些优化。
让这个队列成为单调的,这样我们需要最小值的时候,时间复杂度就是O(1);整体复杂度从O(nk)下降到O(n)(实际上还是要比o(n)大一点的);
如何在滑动的过程中,保证这个队列的单调性呢?
入队的时候遍历一遍队伍,找到合适的位置就好了。
写一遍大概就理解了。写这种例题,还是要写注释,再写点笔记,方便以后自己看。
代码如下:
#include <iostream>
using namespace std;
const int N = 1e6+10;
int a[N];
//数组模拟队列
int h,t;
int q[N]; //队列
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,k;
cin >> n >> k;
for(int i = 0;i<n;i++) cin >> a[i];
//队列初始化
h = 0,t = -1;
for(int i = 0;i<n;i++){
//这里是窗口的一些判断条件:1:队列不出错 2:窗口在范围内
if(h<=t && q[h] < i- k+1) h++;
// 该插入那个位置
// 第二个条件有一个等于,不要漏了
while(h<=t && a[q[t]] >= a[i]) t--;
// 存入元素
q[++t] = i;
// 遍历到第n个元素再输出
if(i >= k - 1) cout << a[q[h]]<<" ";
}
cout << endl;
//队列重新初始化
h = 0,t = -1;
for(int i = 0;i<n;i++){
if(h<=t && q[h] < i- k+1) h++;
// 改一下这里的条件就OK了
while(h<=t && a[q[t]] <= a[i]) t--;
q[++t] = i;
if(i >= k - 1) cout << a[q[h]]<<" ";
}
cout << endl;
}
LC209:长度最小的子数组
在ACW上学了算法,怎么复习一下呢,去LC上选好标签,找一题比较热门的写一下就完了。
题意: n个正整数的数组,寻找一个子数组,子数组的和>=taret,求子数组的最小长度。
由于数组都是正整数,加上必会导致和的增大。不太好解释这题。
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int sum = 0,idx = 0; //sum表示队列的和,idx表示队头下标
int result = 200000; //设置eof
// 最近很喜欢用static lambda 把很多操作抽象化,你忽略这两个lambda的话
// 再看后面那个for循环就很舒服了
static auto push = [&](int x){
sum += x;
};
static auto pop = [&](){
sum -= nums[idx];
idx++;
};
for(int i = 0;i<nums.size();i++){
push(nums[i]);
while(sum >= target) {
result = min(result,i-idx+1);
pop();
}
}
return (result == 200000?0:result);
}
};
个人牢骚(建议不要看)
话说,我也不打比赛,确实没有这个打算。那么我一大一的人,写这么多算法题干嘛呢。。。也不找工作。。。,感觉有点浪费时间
但完全不写吧也不对,我想我该衡量每周的题量。毕竟数据结构课的作业的题量也不小,我再刷题。感觉时间投入太多了,不是很好。
话说,最近事情真的很多,没有太多时间搞自己的事情。高数,线代,光是学懂就要在课下又花不少时间,又选了个电路,早知道一门不选,
纯纯浪费我时间。学校终于项目招人了,为了在简历上写点好看的东西,最近还要写个聊天器example上去。还得写简历,也不知道c能不能被选上,
学c的实在太少了。还有基础要补,累啊。累啊。
\$ \$
算法复杂度部分,可以用$O(n)$框住,显示效果会更好,markdown是支持latex语法的
很棒,加油
可以大二去找实习,一份好的实习 > 学校项目
好的,谢谢带佬
加油加油。算法题以后面试都要考的,提前也不要紧,不吃亏。
好的