问CNN多维卷积阵列上最大池运算的最佳时间复杂度

EN

#include <iostream>
#include <vector>
#include <deque>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 1e3;
int g[N][N];

void max_window(int l1, int l2, int r1, int r2, int k) {
    vector<int> nums;

    // Time: max(n, m)
    for (int i = l1; i <= r1; i ++) {
        for (int j = l2; j <= r2; j ++) {
            nums.push_back(g[i][j]);
        }
    }

    vector<int> res;
    deque<int> q;
    for (int i = 0; i < nums.size(); i ++) {
        while (q.size() && i - q.front() >= k) q.pop_front();

        while (q.size() && nums[q.back()] <= nums[i]) q.pop_back();

        q.push_back(i);        
        if (i >= k - 1) res.push_back(nums[q.front()]);
    }

    int cnt = 0;
    for (int i = l1; i <= r1; i ++) {
        for (int j = l2; j <= r2; j ++) {
            if (cnt >= res.size()) break;
            g[i][j] = res[cnt];
            cnt ++;
        }
    }
    return;
}


int main(){
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    #endif

    int n, m, a, b;
    cin >> n >> m >> a >> b;
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < m; j ++) {
            cin >> g[i][j];
        }
    }

    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < m; j ++) {
            cout << g[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;

    // shape: n x m
    for (int i = 0; i < n; i ++) {  
        max_window(i, 0, i, n - 1, b);
    }


    for (int j = 0; j < m - b + 1; j ++) {  // shape：n x (m - b + 1)
        max_window(0, j, m - 1, j, a);
    }

    // shape：(n - a + 1) x (m - b + 1)
    for (int i = 0; i < n - a + 1; i ++) {
        for (int j = 0; j < m - b + 1; j ++) {
            cout << g[i][j] << " ";
        }
        cout << endl;
    }
    
    return 0;
}

5 5 3 3
5 3 2 1 4
2 3 1 5 3
1 2 3 4 6
1 2 3 4 5
5 4 3 2 1

5 3 2 1 4 
2 3 1 5 3
1 2 3 4 6
1 2 3 4 5
5 4 3 2 1

5 5 6
3 5 6
5 4 6