想补充一下关于hh、tt初始化的细节：
- ①hh, tt的初始化是与数组第一个值下标有关的： hh≤数组第一个下标 （如数组从0开始，hh≤0；数组从1开始，hh≤1，可以是1/0/-1等等）
- ②对于数组第一个值下标从0还是从1开始,还会影响输出时的if判断,需要对应修改:
- 下标从0开始，就是i>=k-1，因为第一个窗口为0 1 2；
- 下标从1开始，就是i>=k，因为首个窗口是1 2 3
- ③对于hh是有要求的,但我看到有人说hh和tt之间要间隔1个位不是很明白缘由,我尝试hh和tt同个初始化值是没有影响的,若有明白原因的可以分享一下么?

//情况1:
for(int i=0;i<n;i++) scanf("%d", &a[i]);//数组从0开始存
int hh=0,tt=-1;//√ 至多hh=0,其他hh≤0的数都可以
//int hh=1,tt=0;//× 此时若hh=1就会出错

for(int i=0;i<n;i++){
        if(hh<=tt&&i-k+1>q[hh]) hh++;
        while(hh<=tt&&a[q[tt]]>=a[i]) tt--;
        q[++tt] = i;

        if(i>=k-1) printf("%d ",a[q[hh]]);  //下标从0开始，就是i>=k-1，因为第一个窗口为0 1 2；下标从1开始，就是i>=k，因为首个窗口是1 2 3
    }

//情况2:
for(int i=1;i<=n;i++) scanf("%d", &a[i]);//数组从0开始存
int hh=1,tt=0;//√ 此时至多hh=1开始,
//int hh=0,tt=-1;//√ 其他只要hh≤1的数,如hh=0都可以

for(int i=1;i<=n;i++){
        if(hh<=tt&&i-k+1>q[hh]) hh++;
        while(hh<=tt&&a[q[tt]]>=a[i]) tt--;
        q[++tt] = i;

        if(i>=k) printf("%d ",a[q[hh]]);  //下标从1开始，就是i>=k，因为首个窗口是1 2 3
    }

是因为 数组起始存储的位置不同 ==> 所以①hh和tt②if(i>=k)/if(i>=k-1)才有了不同

刚踩完这个坑就看到了这个评论hhh

我也补充一下，就是如果数组下标从1开始的话，如果第一个if那里像这篇题解一样不加hh<=tt的条件的话，就会被卡最后一个测试点

因为如果没有这个判断条件的话，hh初始值为0，那么i - k +1 得出的结果是 2-k ，而因为q是全局数组，q[hh]的值是0

如果k<2的话，这个if条件就成立了

这就导致我队列里面什么元素都没有，队头又往前了一个位置，也就是hh++

而最后一个过不去的测试点k=1，正好印证了上面的结论(k<2)

下面是被卡的代码

#include<iostream>
// #include<cstring>
// #include<algorithm>
// #include<vector>
// #include<set>
// #include<cstdio>
// #include<sstream>
using namespace std;
const int N=1e6+10,M=1e5+10,MOD=1000000007;
typedef long long LL;
typedef pair<int,int> PII;

int n,k,arr[N],q[N],hh,tt=-1;

int main()
{
//  cin.tie(0),cout.tie(0);
//  ios::sync_with_stdio(0);

    scanf("%d%d",&n,&k);

    for(int i=1;i<=n;i++) scanf("%d",&arr[i]);

    //求最小的
    for(int i=1;i<=n;i++)
    {
        //1.将队头移除
        if( i - q[hh] + 1 >  k  ) ++hh;

        //2.将不满足单调性的从队尾移除
        while( hh<=tt &&  arr[i] <= arr[ q[tt] ]  ) --tt;

        //3.将元素添加到队尾
        q[++tt]=i;

        if(i>=k)
        printf("%d ",arr[q[hh]]);

    }
    hh=0,tt=-1;
    cout<<endl;
    for(int i=1;i<=n;i++)
    {
        if( i-q[hh] +1 >k ) hh++;

        while(hh<=tt && arr[i] >= arr[q[tt]] ) --tt;

        q[++tt] =i;

       if(i>=k)
        printf("%d ",arr[q[hh]]);
    }

    return 0;
}

谢谢你

我hh=1,tt=0可以，跑过了。但是我不明白的是hh<=tt如果是为了保证队列不为空的话，hh<tt不就够了吗，为啥还要hh<=tt呢。

里边有一个元素的话就是hh<=tt如果是hh<tt的话里边就是存两个元素 保证不空就有一个元素就行

hh和tt从什么开始无所谓把，但是要保证，hh=tt+1,（hh>tt）因为while循环中，hh<=tt才能进入循环OwO

我随便测试的是，hh=6,tt=5，也过了qwq

2023.8.7亲测cout不会超时

if (i - k + 1 > q[hh]) ++ hh; 为什么和q[hh]比较呀

因为q[hh]存储的是队头

hh，自问自答

存的是下标

tt不应该从0开始吗？tt从-1开始时当队列入队一个元素时tt==hh==0，这样队列不是空的啊，而你这样不就判断为空了吗？
我把tt换成tt=0ac了
求解答

hh<=tt这个判断条件 有一个元素时候不是空的

有两重循环 为什么时间复杂度是O(N)的？

while 那里只进行一次判断

每个元素最多出队一次，n次for循环while循环次数加起来最多n次

while 改成if会wa

你可以这么想，while那里判断条件最多执行常数次，比如新加入一个最小值，哪怕一直弹出到队首，队列长度才k个，k是常数，所以while最多执行k次，合起来就是O(kN)，化简就是O(N)。

i - k + 1 > q[hh] 这个啥意思，为什么加一 ，为什么大于q[hh]

q存的是下标

i-k+1是滑动窗口第一个元素的下标，q[hh]里面存的是队列头的下标，因为窗口是滑动的，所以队列的头要滑出去，这句是确保滑出去的是队列头。等价于i-k==q[hh]

为什么hh++的判断条件不能写为（ tt - hh > k-1） 呢？
维持的窗口一旦超过窗口范围就要把队头移出去

https://blog.csdn.net/qq_53110416/article/details/127355096?spm=1001.2014.3001.5501纯暴力

暴力好像会超时，我第一次写的暴力和你的差不多一样

讲的真好，看到你的名字我一下就点进来了，很快啊

数组q和i-k+1表示的是什么

q存的是窗口内元素的下表，i - k + 1表示移动窗口中首元素的下标，用来判断当前队头是否已经不在窗口范围内

q[-1]不会出现数组越界吗

这样为什么就错了
#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]
typedef long long ll;
ll arr[100001];
ll M[100001];
ll m[100001];
using namespace std;
int main()
{
ll N,n;
cout<<”分别输入数组的大小和滑动窗口的的大小”<[HTML_REMOVED]>N>>n;
ll i;
for(i=0;i[HTML_REMOVED]>arr[i];
}

for(i=0;i<N-n+1;i++)
{
    vector<ll>brr(arr+i,arr+n+i);       
    sort(brr.begin(),brr.end());
    M[i]=brr[0];
    m[i]=brr[n-1];
}
for(i=0;i<N-n+1;i++)
{
    cout<<M[i]<<" ";
}
cout<<endl;
for(i=0;i<N-n+1;i++)
{
    cout<<m[i]<<" ";
}

return 0;

}

这里的原题链接好像是错的

请问为什么不能求最小值的时候按递减排序，最后输出队尾呀？

这里的tt=-1,是因为下面的++tt吗

请问为什么hh从0开始，数组下标也一定要从0开始存呢？

不一定的，数组下标不一定非得从一开始，只需要改变一下，输出最小的的条件就行了

为什么要存下标啊？

因为要通过下标判断是否出队列，是否超出了限制。

我觉得有两个原因，一是：for循环的是数组下标，不是值；二是：在判断队头是否需要出队时，需要比较数组下标，这样更加的方便

https://blog.csdn.net/m0_74215326/article/details/128835688?spm=1001.2014.3001.5502

懂了懂了感谢感谢

q[-1]的值是啥啊

数组不存在负数下标，直接短路了