154. 滑动窗口
单调队列

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+10;
int a[MAXN];
int q[MAXN];
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);

    int h=0,t=-1;//h头，t尾，新加的数放进尾里
    for(int i=1;i<=n;i++)
    {
        while(h<=t&&a[q[t]]>=a[i])t--;
        q[++t]=i;
        if(i-q[h]+1>k)h++;
        if(i>=k)printf("%d%c",a[q[h]],i==n?'\n':' ');
    }

    h=0,t=-1;
    for(int i=1;i<=n;i++)
    {
        while(h<=t&&a[q[t]]<=a[i])t--;
        q[++t]=i;
        if(i-q[h]+1>k)h++;
        if(i>=k)printf("%d%c",a[q[h]],i==n?'\n':' ');
    }

    return 0;
}

220. 存在重复元素 III
o(nlogn)

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {

        int n=nums.size();
        set<long long>st;
        for(int i=0;i<n;i++)
        {
            auto iter=st.lower_bound(1ll*nums[i]-t);
            if(iter!=st.end()&&*iter<=1ll*nums[i]+t)return true;
            st.insert(nums[i]);
            if(i>=k)st.erase(nums[i-k]);
        }
        return false;
    }
};

o(n)把每 t+1 个长度的区间看成一个桶，装一个数，如果属于同一个桶，差值肯定小于等于t，再看左右两边的桶的值是否符合条件

class Solution {
public:
    long long getid(long long x,long w)
    {
        return x<0? (1ll*x+1ll)/w-1 : x/w ; //注意负数的映射
    }
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        unordered_map<long long,long long>mp;
        int n=nums.size();
        for(int i=0;i<n;i++)
        {
            long long x=nums[i];
            int id=getid(x,1ll*t+1ll);
            if(mp.count(id))return true;
            if(mp.count(id-1)&&abs(x-mp[id-1])<=t)return true;
            if(mp.count(id+1)&&abs(x-mp[id+1])<=t)return true;
            mp[id]=x;
            if(i>=k)mp.erase(getid(nums[i-k],1ll*t+1ll));
        }
        return false;
    }
};