滑动窗口最大值 稀疏表 spare table
程序员文章站
2022-06-07 16:53:24
...
题目描述
给定一个数组和滑动窗口的大小,找出所有滑动窗口里数值的最大值。例如,如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3,那么一共存在6个滑动窗口,他们的最大值分别为{4,4,6,6,6,5}; 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个: {[2,3,4],2,6,2,5,1}, {2,[3,4,2],6,2,5,1}, {2,3,[4,2,6],2,5,1}, {2,3,4,[2,6,2],5,1}, {2,3,4,2,[6,2,5],1}, {2,3,4,2,6,[2,5,1]}。
记数组dp[i][j]
表示[i,i+2j-1]区间内的最大值
显然dp[i][0]=num[i]
,在此基础之上我们对j!=0的情况进行递推
对于dp[i][j]
我们可分成两块区域[i,i+2j-1-1]和[2j-1+i,i+2j-1],显然所求区间最值就是这两个子区间的最值
因此有递推式
附样例的建表过程
对ST表的查询是该结构最精妙的地方。我们所构建的ST表只能记录长度为2的整数次幂长度的区间最值,对于任意长度的区间我们又该怎么办呢?
重叠部分查询位置。显然重叠部分位置是不会对结果造成影响的,所以对于给定查询区间长度n,首先记k=(int)log2(n)
,即2k为不大于n的最大幂次,随后我们分别从区间头和区间尾取长度为2k长度的区间,合并两个子区间上最值就是查询结果了
class Solution {
public:
vector<int> maxInWindows(const vector<int>& num, unsigned int w)
{
vector<int> ans;
int len=num.size();
int k=lesspow2(w);
if(len==0 || w==0)
return ans;
vector<vector<int> > dp(len,vector<int>(k+1));
for(int i=0;i<len;i++)
dp[i][0]=num[i];
for(int j=1;j<=k;j++){
for(int i=0;i<len-pow(2,j)+1;i++){
dp[i][j]=max(dp[i][j-1],dp[i+pow(2,j-1)][j-1]);
}
}
for(int i=0;i<len-w+1;i++){
int maxn=max(dp[i][k],dp[i+w-pow(2,k)][k]);
ans.push_back(maxn);
}
return ans;
}
int lesspow2(int n){
int p=0,cnt=1;
while(n>=cnt)
p++,cnt*=2;
return p-1;
}
/*
int pow(int b,int e){
int ans=1;
while(e--){
ans=ans*b;
}
return ans;
}
*/
};
上一篇: 程序设计思维 A - 化学
下一篇: 习题6-7 简单计算器 (20分)