Record

在1D的时候这个写法通过了滑动窗口的数据的（Record and code）

#include <bits/stdc++.h>

using namespace std;

const int MAXN=1e3+10;

int a[MAXN][MAXN];
int rmin[MAXN][MAXN], rmax[MAXN][MAXN]; 
deque<int> q; // deque stores the position (instead of value)
// rmin[i][j] stands for the minimum between [i][j-l+1],[i][j]
// cmin[i][j] stands for the minimum between [i-l+1][j-l+1],[i][j]
int cmin[MAXN][MAXN], cmax[MAXN][MAXN]; 
int n, m, l, ans=1e9+1;

int main() {
    cin>>n>>m>>l;
    for (int i=1; i<=n; ++i) {
        for (int j=1; j<=m; ++j) cin>>a[i][j];
    }
    for (int i=1; i<=n; ++i) {
        q.clear();
        for (int j=1; j<=m; ++j) {
            if (q.size() && a[i][j]<=a[i][q.front()]) q.clear();
            while (q.size() && 
                (q.front()<j-l+1)) q.pop_front();
            while (q.size() && 
                (q.back()<j-l+1 || a[i][q.back()]>=a[i][j])) 
                q.pop_back();
            q.push_back(j);
            rmin[i][j]=a[i][q.front()];
            // min for every rows
        }
    }

    for (int i=1; i<=n; ++i) {
        q.clear();
        for (int j=1; j<=m; ++j) {
            if (q.size() && a[i][j]>=a[i][q.front()]) q.clear();
            while (q.size() && 
                (q.front()<j-l+1)) q.pop_front();
            while (q.size() && 
                (q.back()<j-l+1 || a[i][q.back()]<=a[i][j])) q.pop_back();
            q.push_back(j);
            rmax[i][j]=a[i][q.front()];
            // max for every rows
        }
    }

    for (int j=1; j<=m; ++j) {
        q.clear();
        for (int i=1; i<=n; ++i) {
            if (q.size() && rmin[i][j]<=rmin[q.front()][j]) q.clear();
            while (q.size() && 
                (q.front()<i-l+1)) q.pop_front();
            while (q.size() && 
                (q.back()<i-l+1 || rmin[i][j]<=rmin[q.back()][j])) q.pop_back();
            q.push_back(i);
            cmin[i][j]=rmin[q.front()][j];
        }
    }

    for (int j=1; j<=m; ++j) {
        q.clear();
        for (int i=1; i<=n; ++i) {
            if (q.size() && rmax[i][j]>=rmax[q.front()][j]) q.clear();
            while (q.size() && 
                (q.front()<i-l+1)) q.pop_front();
            while (q.size() && 
                (q.back()<i-l+1 || rmax[i][j]>=rmax[q.front()][j])) q.pop_back();
            q.push_back(i);
            cmax[i][j]=rmax[q.front()][j];
        }

    }
    for (int i=l; i<=n; ++i) {
        for(int j=l; j<=m; ++j) ans=min(ans,cmax[i][j]-cmin[i][j]);
    }
    cout<<ans;
}