【数据结构】单调队列

单调队列

单调队列是主要用于解决类似滑动窗口类问题的数据结构：在长度为 $n$ 的序列中，求每个长度为 $m$ 的区间的区间最值问题，时间复杂度为 $O(n)$

deque<int> q;
int v[N];
int n,m;
int main(){
    cin >> n >> m;
    for (int i = 1;i <= n;++i){
        cin >> v[i];
    }
    for (int i = 1;i <= n;++i){
        if (!q.empty() && i - q.front() >= m)
            q.pop_front();
        while (!q.empty() && v[q.back()] < v[i])
            q.pop_back();
        q.push_back(i);
        if (i >= m)
            cout << v[q.front()] << " ";
    }
    return 0;
}

如果是求最小值就v[i] < v[q.back()]

二维单调队列

求 $a\times b$ 矩阵中所有 $n\times n$ 区域中的最小值或者最大值。

朴素做法 $O(abn^2)$

单调队列优化 $O(ab)$

先用单调队列处理行最值，再用处理好的行最值处理列最值

最终得到的就是 $n\times n$ 的最值

int a,b,n;
int d[N][N];
int vmin[N][N],vmax[N][N];
int lmin[N][N],lmax[N][N];
deque<int> q;
deque<int> t;
int main(){
    cin >> a >> b >> n;
    for (int i = 1;i <= a;++i){
        for (int j = 1;j <= b;++j){
            cin >> d[i][j];
        }
    }
    int h = 0,k = 0;
    for (int i = 1;i <= a;++i){
        h = 0;
        q.clear();
        for (int j = 1;j <= b;++j){
            if (!q.empty() && j - q.front() >= n)
                q.pop_front();
            while (!q.empty() && d[i][q.back()] < d[i][j])
                q.pop_back();
            q.push_back(j);
            if (j >= n)
                vmax[i][++h] = d[i][q.front()];
        }
    }

    for (int i = 1;i <= a;++i){
        k = 0;
        t.clear();
        for (int j = 1;j <= b;++j){
            if (!t.empty() && j - t.front() >= n)
                t.pop_front();
            while (!t.empty() && d[i][t.back()] > d[i][j])
                t.pop_back();
            t.push_back(j);
            if (j >= n)
                vmin[i][++k] = d[i][t.front()];
        }
    }

    int hh = 0,kk = 0;
    for (int j = 1;j <= k;++j){
        hh = kk = 0;
        q.clear();
        t.clear();
        for (int i = 1;i <= a;++i){
            if (!q.empty() && i - q.front() >= n)
                q.pop_front();
            while (!q.empty() && vmax[q.back()][j] < vmax[i][j])
                q.pop_back();
            q.push_back(i);
            if (i >= n)
                lmax[++hh][j] = vmax[q.front()][j];

            if (!t.empty() && i - t.front() >= n)
                t.pop_front();
            while (!t.empty() && vmin[t.back()][j] > vmin[i][j])
                t.pop_back();
            t.push_back(i);
            if (i >= n)
                lmin[++kk][j] = vmin[t.front()][j];
        }
    }

    int minn = INF;
    for (int i = 1;i <= kk;++i){
        for (int j = 1;j <= k;++j){
            minn = min(minn,lmax[i][j] - lmin[i][j]);
        }
    }

    cout << minn << endl;
    return 0;
}