摘要:思路一暴力循环如果我们将矩阵中的每个子矩阵都枚举出来,并计算其元素和,从而得出小于的最大值即可。
题目要求
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思路二:利用二分法思路进行优化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
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)]换句话说,假如将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思路三:分治法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
treeSet = new TreeSet (); 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的整数数组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 ; startColmid) { ans = Math.max(sums[j-1] - sums[i], ans); if (ans == k) return k; } while(m
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/74850.html
摘要:题目链接参考里的解释先是如何在矩阵里找的问题,参考视频然后就是一个里面找不大于的最大值问题了要找到最大的用就是,就是来做了。行和列哪个打就用另一个扫。另外找最大不超过的还可以用,参考 363. Max Sum of Rectangle No Larger Than K 题目链接:https://leetcode.com/problems... 参考discussion里的解释:http...
Problem Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isnt one, return 0 instead. Note The sum of the entire nums array is guaranteed to fit ...
摘要: Problem In a given array nums of positive integers, find three non-overlapping subarrays with maximum sum. Each subarray will be of size k, and we want to maximize the sum of all 3*k entries. R...
Problem For a web developer, it is very important to know how to design a web pages size. So, given a specific rectangular web page’s area, your job by now is to design a rectangular web page, whose l...
摘要:题目要求代表对数组在位置上进行顺时针的旋转后生成的数组。暴力循环按照题目的要求,执行两次循环即可以获得的所有值,只需要从中比较最大值即可。 题目要求 Given an array of integers A and let n to be its length. Assume Bk to be an array obtained by rotating the array A k p...
阅读 3565·2023-04-25 14:20
阅读 1178·2021-09-10 10:51
阅读 1145·2019-08-30 15:53
阅读 452·2019-08-30 15:43
阅读 2307·2019-08-30 14:13
阅读 2784·2019-08-30 12:45
阅读 1198·2019-08-29 16:18
阅读 1154·2019-08-29 16:12