专栏首页眯眯眼猫头鹰的小树杈leetcode363. Max Sum of Rectangle No Larger Than K

leetcode363. Max Sum of Rectangle No Larger Than K

题目要求

Given a non-empty 2D matrix matrix and an integer k, find the max sum of a rectangle in the matrix such that its sum is no larger than k.

Example:

Input: matrix = [[1,0,1],[0,-2,3]], k = 2
Output: 2 
Explanation: Because the sum of rectangle [[0, 1], [-2, 3]] is 2,
             and 2 is the max number no larger than k (k = 2).

Note:

1. The rectangle inside the matrix must have an area > 0.
2. What if the number of rows is much larger than the number of columns?

现有一个由整数构成的矩阵,问从中找到一个子矩阵,要求该子矩阵中各个元素的和为不超过k的最大值,问子矩阵中元素的和为多少? 注:后面的文章中将使用[左上角顶点坐标,右下角顶点坐标]来表示一个矩阵,如[(1,2),(3,4)]表示左上角顶掉坐标为(1,2),右下角顶点坐标为(3,4)的矩阵。用S[(1,2),(3,4)]表示该矩阵的面积。顶点的坐标系以数组的起始点作为起点,向下为x轴正方向,向右为y轴正方向。

思路一:暴力循环

如果我们将矩阵中的每个子矩阵都枚举出来,并计算其元素和,从而得出小于K的最大值即可。 这里通过一个额外的二维数组S缓存了[(0,0), (i,j)]的矩形的面积,可以通过O(n^2)的时间复杂度完成计算,即S[i][j] = matrix[i][j] + S[i-1][j] + S[i][j-1] - S[i-1][j-1], 则矩形[(r1,c1),(r2,c2)]的面积为S[r2][c2] -S[r1-1][c2] - S[r2][c1-1] + S[r1-1][c1-1]。这种算法的时间复杂度为O(N^4),因为需要定位矩形的四个顶点,一共需要四圈循环,代码如下:

    public int maxSumSubmatrix(int[][] matrix, int k) {
        int row = matrix.length;
        if(row == 0) return 0;
        int col = matrix[0].length;
        if(col == 0) return 0;
        
        //rectangle[i][j]记录顶点为[0,0],[i,j]的矩形的面积
        int[][] rectangle = new int[row][col];
        for(int i = 0 ; i<row ;  i++) {
            for(int j = 0 ; j<col ; j++) {
                int area = matrix[i][j];
                if(i>0) {
                    area += rectangle[i-1][j];
                }
                if(j>0) {
                    area += rectangle[i][j-1];
                }
                //减去重复计算的面积
                if(i>0 && j>0) {
                    area -= rectangle[i-1][j-1];
                }
                
                rectangle[i][j] = area;
            }
        }
        
        
        int result = Integer.MIN_VALUE;
        for(int startRow = 0 ; startRow<row; startRow++) {//矩形的起点行
            for(int endRow = startRow ; endRow<row ; endRow++) {//矩形的结束行
                for(int startCol = 0 ; startCol<col ; startCol++) {//矩形的起始列
                    for(int endCol = startCol ; endCol<col ; endCol++) {//矩形的结束列
                        int area = rectangle[endRow][endCol];
                        if(startRow > 0) {
                            area -= rectangle[startRow-1][endCol];
                        }
                        if(startCol > 0) {
                            area -= rectangle[endRow][startCol-1];
                        }
                        if(startRow > 0 && startCol > 0) {
                            area += rectangle[startRow-1][startCol-1];
                        }
                        if (area <= k)
                            result = Math.max(result, area);
                    }
                }
            }
        }
        return result;
    }

思路二:利用二分法思路进行优化

对算法从时间上优化的核心思路就是尽可能的减少比较或是计算的次数。上面一个思路的我们可以理解为以row1和row2分别作为子矩阵的上边界和下边界,以col2作为右边界,要求找到一个左边界col1,使得其划分出来的子矩阵中元素的和为小于等于k的最大值,即

max(S[(row1,0),(row2, col2)] - S[(row1,0),(row2, col1)]) 
&& col1 < col2 
&& S[(row1,0),(row2, col2)] - S[(row1,0),(row2, col1)]<k`。

换句话说,假如将col2左侧的所有以最左侧边为起点的子矩阵按照元素和从小到大排队,即将子矩阵(row1, 0), (row2, colx) 其中colx < col2按照元素和从小到大排序,此时只需要在该结果中找到一个矩阵,其值为大于等于S[(row1,0),(row2, col2)] - k的最小值。此时得出的矩阵元素和差最大。这里采用TreeSet来实现O(logN)的元素查找时间复杂度。

代码如下:

    public int maxSumSubmatrix2(int[][] matrix, int k) {
        int row = matrix.length;
        if(row == 0) return 0;
        int col = matrix[0].length;
        if(col == 0) return 0;
        
        //rectangle[i][j]记录顶点为[0,0],[i,j]的矩形的面积
        int[][] rectangle = new int[row][col];
        for(int i = 0 ; i<row ;  i++) {
            for(int j = 0 ; j<col ; j++) {
                int area = matrix[i][j];
                if(i>0) {
                    area += rectangle[i-1][j];
                }
                if(j>0) {
                    area += rectangle[i][j-1];
                }
                //减去重复计算的面积
                if(i>0 && j>0) {
                    area -= rectangle[i-1][j-1];
                }
                
                rectangle[i][j] = area;
            }
        }
        
        
        int result = Integer.MIN_VALUE;
        for(int startRow = 0 ; startRow < row ; startRow++) {
            for(int endRow = startRow ; endRow < row ; endRow++) {
                //记录从startRow到endRow之间所有以最左侧边为起点的矩形的面积
                TreeSet<Integer> treeSet = new TreeSet<Integer>();
                treeSet.add(0);
                for(int endCol = 0 ; endCol < col ; endCol++) {
                    int area = rectangle[endRow][endCol];
                    if(startRow > 0) {
                        area -= rectangle[startRow-1][endCol];
                    }
                    //可以减去的左侧矩形的最小面积,即大于S[(row1,0),(row2, col2)] - k的最小值
                    Integer remain = treeSet.ceiling(area - k);
                    if(remain != null) {
                        result = Math.max(result, area - remain);
                    }
                    treeSet.add(area);
                }
            }
        }
        return result;
    }

思路三:分治法

从上面两种思路,我们可以将题目演化成另一种思路,即对于任意以row1和row2作为上下边界的子矩阵,将其中每一列的元素的和记为sum[colx](0<=colx<col),则生成一个长度为col的整数数组sum。需要从该整数数组中找到一个连续的子数组,使得该子数组的和最大且不超过k。

连续子数组的和是一道非常经典的动态规划的问题,它可以在nlogn的时间复杂度内解决。这里采用归并排序的思路来进行解决。本质上将数组以中间位置分割为左子数组和右子数组,分别求左子数组内和右子数组内最大的连续子数组和,并且在递归的过程中将左右子数组中的元素分别从小到大排序。接着判断是否有横跨中间节点的子数组满足题目要求,因为左右子数组分别有序,因此一旦遇到一个右边界,其和左边界构成的矩阵的元素的和超过k,就可以停止右指针的移动。因此每次中间结果的遍历只需要O(N)的时间复杂度。

代码如下:

    public int maxSumSubmatrix3(int[][] matrix, int k) {
        int row = matrix.length;
        if(row == 0) return 0;
        int col = matrix[0].length;
        if(col == 0) return 0;
        int result = Integer.MIN_VALUE;
        int[] sums = new int[row+1];//sums[i]记录startCol到endCol列之间,0行到i行构成的矩阵的面积
        for(int startCol = 0 ; startCol<col ; startCol++) {
            int[] sumInRow = new int[row];//sumInRow[i]记录startCol到endCol列之间第i行所有元素的和
            for(int endCol = startCol; endCol<col ; endCol++) {
                for(int endRow = 0 ; endRow<row ; endRow++) {
                    sumInRow[endRow] += matrix[endRow][endCol];
                    sums[endRow+1] = sums[endRow] + sumInRow[endRow];
                }
                //对startCol到endCol列之间所有的矩阵元素和构成的数组通过分治法找到最大的连续子数组
                result = Math.max(result, mergeSort(sums, k, 0, sums.length));
                if(result == k) return k;
            }
        }
        return result;
    }
    
    public int mergeSort(int[] sums, int k, int start, int end) {
        //矩阵数组至少包含一个元素
        if(end <= start + 1) return Integer.MIN_VALUE;
        int mid = start + (end - start)/2, cacheIndex = 0;
        //对左侧递归计算,此时sums数组[start,mid)之间的元素已经有序
        int ans = mergeSort(sums, k,  start, mid);
        if(ans == k) return k;
        //对右侧递归计算,此时sums数组[mid,end)之间的元素已经有序
        ans = Math.max(ans, mergeSort(sums, k, mid, end));
        //缓存sums数组[start,end)之间排序的结果
        int[] sortedSubSums = new int[end - start];
        if(ans == k) return k;
        for(int i = start, j = mid, m = mid ; i<mid ;  i++) {
            while(j<end && sums[j] - sums[i] <= k) j++;//找到第一个满足[i,j)之间的元素和大于k,[i,j-1)之间的元素和小于等于k的连续子数组
            if(j > mid) {
                ans = Math.max(sums[j-1] - sums[i], ans);
                if (ans == k) return k;
            }
            while(m<end && sums[m] < sums[i]) sortedSubSums[cacheIndex++] = sums[m++];//排序,通过每次将中间位置右侧比左侧当前位置小的元素全部复制有序数组缓存中
            sortedSubSums[cacheIndex++] = sums[i];
        }
        System.arraycopy(sortedSubSums, 0, sums, start, cacheIndex);
        return ans;
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 395. Longest Substring with At Least K Repeating Characters

    这是一个经典的分治法解决的问题,关键在于我们如何将这个问题分解为更小的子问题。反过来想,这个子字符串一定不包含什么元素呢?当一个元素出现的总次数小于k,那么该元...

    眯眯眼的猫头鹰
  • leetcode540. Single Element in a Sorted Array

    You are given a sorted array consisting of only integers where every element app...

    眯眯眼的猫头鹰
  • 547. Friend Circles

    There are N students in a class. Some of them are friends, while some are not. T...

    眯眯眼的猫头鹰
  • 适合数据分析面试笔试入门的编程题

    1.在输入ai1的时候,因为是每颗果树的第一个输入,代表刚开始果树的苹果含量,所以可以写在第二个循环的前面和第一个循环的里面,所以第二个循环就要从1开始。

    开心鸭
  • 分治算法

    // 二分查找的思路,halfLen 是中位数的right 所以必须 m + n + 1 // 中位数是可以将数组分割为左右相等的数组,一个数将其分为左右相等...

    黑白格
  • 算法学习记录

    MiChong
  • HDU 3450 Counting Sequences(线段树)

    Counting Sequences Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 3276...

    ShenduCC
  • gcd,哈希问题-LeetCode 357、355、365、367、380

    给定一个非负整数 n,计算各位数字都不同的数字 x 的个数,其中 0 ≤ x < 10n 。

    算法工程师之路
  • L3-004. 肿瘤诊断

    在诊断肿瘤疾病时,计算肿瘤体积是很重要的一环。给定病灶扫描切片中标注出的疑似肿瘤区域,请你计算肿瘤的体积。

    指点
  • 天梯赛 大区赛 L3-014.周游世界 (Dijkstra)

    L3-014. 周游世界 时间限制 200 ms 内存限制 65536 kB 代码长度限制 8000 B 判题程序 Standar...

    ShenduCC

扫码关注云+社区

领取腾讯云代金券