leetcode：面试题 17.24. 最大子矩阵

题目

给定一个正整数、负整数和 0 组成的 N × M 矩阵，编写代码找出元素总和最大的子矩阵。
返回一个数组 [r1, c1, r2, c2]，其中 r1, c1 分别代表子矩阵左上角的行号和列号，r2, c2 分别代表右下角的行号和列号。若有多个满足条件的子矩阵，返回任意一个均可。
注意：本题相对书上原题稍作改动

示例：

  1. 输入：
  2. [
  3.    [-1,0],
  4.    [0,-1]
  5. ]
  6. 输出：[0,1,0,1]
  7. 解释：输入中标粗的元素即为输出所表示的矩阵

解答 & 代码

解法一：二维前缀和 + 最大子数组和

class Solution {
public:
    vector<int> getMaxMatrix(vector<vector<int>>& matrix) {
        int rows = matrix.size();
        int cols = matrix[0].size();
        // 1. 求二维矩阵和，preSumMatrix[i][j] 代表矩阵 [0, 0, i - 1, j - 1] 的元素和
        // 注意下面的处理方式，避免了对边界条件的处理
        vector<vector<int>> preSumMatrix(rows + 1, vector<int>(cols + 1, 0));
        for(int i = 1; i <= rows; ++i)
        {
            for(int j = 1; j <= cols; ++j)
                preSumMatrix[i][j] = preSumMatrix[i - 1][j] + preSumMatrix[i][j - 1] - preSumMatrix[i - 1][j - 1] + matrix[i - 1][j - 1];
        }

        // 2. 用最大子数组和的思想求最大子矩阵
        int maxSum = INT_MIN;                // 最大子矩阵的元素和
        vector<int> result = {0, 0, 0, 0};    // 最大子矩阵的左上角行号、列号、右下角行号、列号
        for(int up = 1; up <= rows; ++up)                // 子矩阵上边界 up
        {
            for(int down = up; down <= rows; ++down)    // 子矩阵下边界 down
            {
                // 对于限定的上边界 up 和下边界 down，求最大子矩阵（求最大子数组和的思想）
                int preSum = 0;        
                int left = 1;        // 最大子矩阵的左边界
                for(int right = 1; right <= cols; ++right)    // 子矩阵右边界
                {
                    // 计算 right 这列的和
                    int curColSum = preSumMatrix[down][right] - preSumMatrix[down][right - 1] - preSumMatrix[up - 1][right] + preSumMatrix[up - 1][right - 1];
                    // 如果前缀和小于 0
                    if(preSum < 0)
                    {
                        left = right;
                        preSum = curColSum;
                    }
                    // 如果前缀和大于 0
                    else
                        preSum += curColSum;

                    // 更新最大子矩阵的面积以及坐标
                    if(preSum > maxSum)
                    {
                        maxSum = preSum;
                        result = {up - 1, left - 1, down - 1, right - 1};
                    }
                }
            }
        }

        return result;
    }
};

复杂度分析：设 m 行 n 列

  • 时间复杂度[困难] 面试题 17.24. 最大子矩阵 - 图1：
  • 空间复杂度 O(mn)：

执行结果：

执行结果：通过

执行用时：376 ms, 在所有 C++ 提交中击败了 11.73% 的用户
内存消耗：13.5 MB, 在所有 C++ 提交中击败了 32.32% 的用户

解法二：一维前缀和+最大子数组和

class Solution {
public:
    vector<int> getMaxMatrix(vector<vector<int>>& matrix) {
        int rows = matrix.size();
        int cols = matrix[0].size();

        int maxSum = INT_MIN;
        vector<int> result = {0, 0, 0, 0};
        for(int up = 0; up < rows; ++up)                // 子矩阵的上边界
        {
            // 每一列的和（从上边界到下边界范围内），每次上边界变化时都要重新清零
            vector<int> colSumList(cols, 0);
            for(int down = up; down < rows; ++down)        // 子矩阵的下边界
            {
                // 更新每一列的和
                for(int col = 0; col < cols; ++col)
                    colSumList[col] += matrix[down][col];

                // 求每列和 colSumList 的最大子数组和
                int preSum = 0;
                int left = 0;                            // 最大子矩阵的左边界
                for(int right = 0; right < cols; ++right)    // 最大子矩阵的右边界
                {
                    if(preSum < 0)
                    {
                        left = right;
                        preSum = colSumList[right];
                    }
                    else
                        preSum += colSumList[right];

                    if(preSum > maxSum)
                    {
                        maxSum = preSum;
                        result = {up, left, down, right};
                    }
                }
            }
        }

        return result;
    }
};

复杂度分析：设 m 行 n 列

  • 时间复杂度[困难] 面试题 17.24. 最大子矩阵 - 图2：
  • 空间复杂度 O(n)：

执行结果：

执行结果：通过

执行用时：183 ms, 在所有 C++ 提交中击败了 61.22% 的用户
内存消耗：13.3 MB, 在所有 C++ 提交中击败了 53.65% 的用户