剑指 Offer 59 - I. 滑动窗口的最大值 - 力扣（Leetcode）
一.分析
方法一：
数组长度为1e5，k的大小为1e4，因此直接暴力计算会TLE。我们可以思考一个更复杂的问题：询问任意区间中的最值。对于该题，可以等价询问数组长度次的最值，如果能将每次询问的复杂度控制在logN以内，就可以解决该问题。
而对于区间最值我们可以使用线段树（logN），树状数组（logNlogN），稀疏数组（1）等数据结构。
- 树状数组
树状数组
class Solution {
public:
int b[100005];
int n;
const int inf=-0x3f3f3f3f;
int lowbit(int x)
{
return x&(-x);
}
void update(int pos,vector<int>& a)
{
while(pos<=n)
{
b[pos]=a[pos-1];
for (int i=1;i<lowbit(pos);i<<=1)
{
b[pos]=max(b[pos],b[pos-i]);
}
pos+=lowbit(pos);
}
}
int query(int l,int r,vector<int>& a)
{
int ans=inf;
while(l<=r)
{
ans=max(ans,a[r-1]);
r--;
while (l<=r-lowbit(r))
{
ans=max(ans,b[r]);
r-=lowbit(r);
}
}
return ans;
}
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
n=nums.size();
vector<int> ans;
for (int i=1;i<=n;i++)
{
b[i]=inf;
}
for (int i=0;i<nums.size();i++)
{
update(i+1,nums);
}
// for (int i=1;i<=n;i++)
// {
// cout<<b[i]<<" ";
// }
for (int i=k;i<=n;i++)
{
ans.push_back(query(i-k+1,i,nums));
}
return ans;
}
};
- 稀疏数组
稀疏数组
class Solution {
public:
const int static maxn=200005;
int st[maxn][17];
int Log2[maxn];
int n;
void init()
{
for (int i=1;i<n+10;i++)
Log2[i]=Log2[i>>1]+1;
}
void prepro(vector<int>& nums)
{
for (int i=0;i<n;i++)
st[i][0]=nums[i];
//cout<<st[2][0]<<endl;
for (int i=1;i<=Log2[n-1];i++)
{
for (int j=0;j<=n-(1<<i);j++)
{
st[j][i]=max(st[j][i-1],st[j+(1<<(i-1))][i-1]);
}
}
}
int query(int l,int r)
{
// cout<<l<<"----"<<r<<endl;
// cout<<Log2<<endl;
return max(st[l][Log2[r-l+1]-1],st[1+r-(1<<(Log2[r-l+1]-1))][Log2[r-l+1]-1]);
}
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
n=nums.size();
init();
//cout<<st[2][0]<<endl;
prepro(nums);
vector<int> ans;
for (int i=0;i<n-k+1;i++)
{
ans.push_back(query(i,i+k-1));
}
//ans.push_back(query(2,4));
return ans;
}
};
方法二：
考虑滑动窗口向右移动过程中下标为i和j的元素，i<j, 若nums[i] < nums[j]，那么num[i]就不可能是滑动窗口中的最大值了。因为若i在滑动窗口中，那么j肯定在滑动窗口中。因此可以维护一个双向队列，当向右移动时，添加元素应该保证队列的严格单调递减（如违反，则从队尾删除元素，类似单调栈）。同时还要保证队列中的元素在滑动窗口中，若不在，从队头删除元素。
复杂度分析：数组中的每个元素都入队一次，出队一次，时间复杂度为O（n），空间复杂度为双向队列的长度O（k）
双向队列
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<pair<int,int>> q;
vector<int> ans;
for (int i=0;i<nums.size();i++)
{
while (q.size() and q.back().second<nums[i])
{
q.pop_back();
}
q.push_back(pair(i,nums[i]));
while (q.size() and q.front().first<i-k+1)
{
q.pop_front();
}
if (i>=k-1)
ans.push_back(q.front().second);
}
return ans;
}
};