二维的滑动窗口最大值

摘要: 滑动矩形窗口最大值

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

滑动窗口最大值问题是单调队列的最典型使用场景，单调队列也是定长滑动窗口问题的最优解法，时间复杂度为 $O(N)$，参考文章 力扣239-滑动窗口最大值。

本文我们将一维上的滑动窗口最大值扩展到二维。

滑动矩形最大值问题

二维上的滑动窗口最大值，有点类似于深度学习里面的一个基本组件：最大池化。只是最大池化中的核很小，而滑动矩形最大值的矩形可能比较大，在分析算法时间复杂度时需要考虑。

二维转一维

二维版本的算法完全在已经解决的一维问题的基础上进行，最终会直接调用一维版本的接口：

vector<int> maxSlidingWindow(const vector<int>& nums, int k)

矩阵的转置

中间需要用到一个组件：矩阵的转置。

// 矩阵转置
vector<vector<int> > transpose(const vector<vector<int> >& matrix)
{
    if(matrix.empty()) return vector<vector<int> >();
    int n = matrix.size(), m = matrix[0].size();
    vector<vector<int> > transposed(m, vector<int>(n, -1));
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < m; ++j)
            transposed[j][i] = matrix[i][j];
    return transposed;
}

算法流程

算法的流程如下：

step1: 对 matrix 的每一行，求一维的滑动窗口最大值，k 是核的宽，得到中间结果 row_result。

step2: 将 row_result 转置，得到 row_result_transposed。

step3: 对 row_result_transposed 的每一行，实际是 row_result 的每一列，再求一遍一维的滑动窗口最大值，k 是核的高，得到结果 result_transposed。

step4: 将结果再转置回来，得到 result。

总时间复杂度 $O(N^{2})$，因为每个元素至少都要访问一遍，$O(N^{2})$ 是最好的时间复杂度了。

// 二维的滑动窗口最大值
vector<vector<int> > max_pooling(const vector<vector<int> >& matrix, int k_row, int k_col)
{
    vector<vector<int> > row_result;
    for(const vector<int>& row_vals: matrix)
        row_result.push_back(maxSlidingWindow(row_vals, k_col));
    vector<vector<int> > row_result_transposed = transpose(row_result);
    vector<vector<int> > result_transposed;
    for(const vector<int>& col_vals: row_result_transposed)
        result_transposed.push_back(maxSlidingWindow(col_vals, k_row));
    vector<vector<int> > result = transpose(result_transposed);
    return result;
}

结果如下：

完整代码 (C++)

$O(N^{2})$

#include <vector>
#include <iostream>
#include <random>
#include <deque>

using namespace std;

// 滑动窗口最大值
vector<int> maxSlidingWindow(const vector<int>& nums, int k) {
    if(nums.empty()) return vector<int>();
    int n = nums.size();
    if(n <= k)
    {
        int mx = nums[0];
        for(int i = 1; i < n; ++i)
            mx = max(mx, nums[i]);
        return vector<int>({mx});
    }
    // 滑动 n - k 次
    // 0..k-1
    deque<int> dq;
    vector<int> result;
    for(int i = 0; i < k; ++i)
    {
        // 插入 i 前先出队
        while(!dq.empty() && nums[dq.back()] <= nums[i])
            dq.pop_back();
        dq.push_back(i);
    }
    result.push_back(nums[dq.front()]);
    for(int i = k; i < n; ++i)
    {
        if(!dq.empty() && dq.front() <= i - k)
            dq.pop_front();
        while(!dq.empty() && nums[dq.back()] <= nums[i])
            dq.pop_back();
        dq.push_back(i);
        result.push_back(nums[dq.front()]);
    }
    return result;
}

// 矩阵转置
vector<vector<int> > transpose(const vector<vector<int> >& matrix)
{
    if(matrix.empty()) return vector<vector<int> >();
    int n = matrix.size(), m = matrix[0].size();
    vector<vector<int> > transposed(m, vector<int>(n, -1));
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < m; ++j)
            transposed[j][i] = matrix[i][j];
    return transposed;
}

// 二维的滑动窗口最大值
vector<vector<int> > max_pooling(const vector<vector<int> >& matrix, int k_row, int k_col)
{
    vector<vector<int> > row_result;
    for(const vector<int>& row_vals: matrix)
        row_result.push_back(maxSlidingWindow(row_vals, k_col));
    vector<vector<int> > row_result_transposed = transpose(row_result);
    vector<vector<int> > result_transposed;
    for(const vector<int>& col_vals: row_result_transposed)
        result_transposed.push_back(maxSlidingWindow(col_vals, k_row));
    vector<vector<int> > result = transpose(result_transposed);
    return result;
}

int main()
{
    default_random_engine dre;
    const int lower = 0;
    const int upper = 255;
    uniform_int_distribution<int> random_pixel(lower, upper);
    int row, col;
    cout << "enter the row and col of matrix: " << endl;
    cin >> row >> col;
    vector<vector<int> > matrix(row, vector<int>(col, -1));
    for(int i = 0; i < row; ++i)
        for(int j = 0; j < col; ++j)
            matrix[i][j] = random_pixel(dre);
    cout << "the matrix: " << endl;
    for(const vector<int> &row_val: matrix)
    {
        for(const int &val: row_val)
            cout << val << " ";
        cout << endl;
    }
    cout << "=====================" << endl;
    cout << "enter the row and col of kernel: " << endl;
    int k_row, k_col;
    cin >> k_row >> k_col;
    vector<vector<int> > max_pooling_result = max_pooling(matrix, k_row, k_col);
    cout << "the result of max pooling: " << endl;
    for(const vector<int> &row_val: max_pooling_result)
    {
        for(const int &val: row_val)
            cout << val << " ";
        cout << endl;
    }
}

---