最大堆+Mp记录位置
为数不多的不看题解过的一个题,时间超越7%也是没谁了
按照 1s处理数据规模最大$10^{7}来计算$
我们建立一个大小为k的堆,用来维护滑动区间里面的数字,堆顶就是最大值了,
每次将区间最左端的数字从堆中删掉,然后将下一个元素推进来即可
要解决的问题:
1.首先是复杂度的问题,每次加入一个元素和删除一个元素,堆调整的代价是log(k)
然后需要调整n次,复杂度大概是n*(logk+logk)
n和代入最大2*10^5*log(10^5)
2.首先堆不支持删除任意位置的元素
要重新搞一下删除任意位置的函数,那么我们首先想到的是,
把数字的位置存起来不就行了吗,弄一个map,记录任意时刻在堆中的位置
3.考虑到数字会重复,所以堆中存的是元素在nums中的下标,并不是元素本身,
mp实际上记录了nums第i个元素在堆数组中的下标
4.堆中加入一个元素:以为堆是一颗满二叉树,所以在最后一个位置放入该元素,然后上浮即可
删除堆顶元素:将最后一个元素覆盖第一个元素,size--,然后堆顶元素下沉
删除指定位置i元素,将最后元素覆盖第i个元素,然后看第i个元素能上浮还是下沉,
注意这里i个元素可能可以上浮,因为该元素可能因为覆盖,
从它本身所在的子树跑到了另一个子树上,父节点不一定比它大
#define debug(x) cout
class Solution {
public:
vectora;
int cnt=0;
vectormp;
bool down(int i,vector&nums){
while(1){
int ma = i;
if(i*2 nums[a[ma]]){
ma = i*2;
}
if(i*2+1 nums[a[ma]]){
ma = i*2+1;
}
if(ma!=i){
swap(a[ma],a[i]);
swap( mp[a[ma]],mp[a[i]] );
i = ma;
}else{
break;
}
}
return true;
}
bool push(int n,vector&nums){
a[++cnt]=n;
mp[n]=cnt;
up(cnt,nums);
return true;
}
bool up(int i,vector&nums){
while(i>1){
int fa = i/2;
if(nums[a[fa]] swap(a[fa],a[i]);
swap( mp[a[fa]],mp[a[i]] );
i = fa;
}else{
break;
}
}
return true;
}
bool remove(int index,vector&nums){
if(index a[index] = a[cnt];
mp[ a[cnt] ] = index;
--cnt;
down(index,nums);
up(index,nums);
}
return true;
}
int top(){
if(cnt>0){
return a[1];
}
return INT_MIN;
}
bool pop(vector&nums){
return remove(1,nums);
}
bool isheap(vector&nums){
for(int i=1;i if(2*i nums[a[i]] ){
return false;
}
if(2*i+1 nums[a[i]] ){
return false;
}
}
return true;
}
vectormaxSlidingWindow(vector & nums, int k) {
int n = nums.size();
a = vector(n+1);
mp = vector(n);
vectorret;
ret.reserve(n);
for(int i=0;ipush(i,nums);
}
ret.push_back( nums[top()]);
for(int i=k;iremove( mp[i-k],nums );
push(i,nums);
ret.push_back( nums[top()]);
}
return ret;
}
};
题解
看了题解之后改用优先队列
#define debug(x) cout
class Solution {
public:
vectormaxSlidingWindow(vector & nums, int k) {
int n = nums.size();
auto cmp = [&](int a,int b){
return nums[a] };
priority_queue,decltype(cmp)> q(cmp);
vectorret;
ret.reserve(n-k+1);
for(int i=0;iq.push(i);
}
ret.push_back( nums[q.top()] );
for(int i=k;iwhile(!q.empty() && q.top() q.pop();
}
q.push(i);
ret.push_back( nums[q.top()] );
}
return ret;
}
};
我用自己写的二叉堆,使用一样的逻辑
发现速度没有stl里面的优先队列快 ,看来有空得读一读源码了^_^
单调栈,单调队列?
单调栈(单调递减的栈)
栈底是最大的元素在nums中的索引
问题的难点在于,每次需要将左端滑出区间的索引删去
但是如果当这个数字滑出区间的时候,还在栈里面,那么它就是栈里最大的数字,
否则该数字应该在单调栈调整的时候就被pop_back了
所以只需要看一下栈底的是不是滑出左边窗口的那个数字,如果是的话直接把栈底的数字扔出去
由于需要对栈底的元素进行操作,所以需要使用一个双端队列,或者vector
#define debug(x) cout
class Solution {
public:
vectormaxSlidingWindow(vector & nums, int k) {
int n = nums.size();
dequeq;
vectorret;
ret.reserve(n-k+1);
for(int i=0;iwhile(!q.empty() && nums[q.back()] q.pop_back();
}
q.push_back(i);
}
ret.push_back( nums[q.front()]);
for(int i=k;iif(i-k == q.front()){
q.pop_front();
}
while(!q.empty() && nums[q.back()] q.pop_back();
}
q.push_back(i);
ret.push_back( nums[q.front()]);
}
return ret;
}
};