【JavaScript】Leetcode每日一题-矩形区域不超过K的最大值和
【JavaScript】Leetcode每日一题-矩形区域不超过K的最大值和
【题目描述】
给你一个 m x n 的矩阵 matrix 和一个整数 k ,找出并返回矩阵内部矩形区域的不超过 k 的最大数值和。
题目数据保证总会存在一个数值和不超过 k 的矩形区域。
示例1:
输入:matrix = [[1,0,1],[0,-2,3]], k = 2
输出:2
解释:蓝色边框圈出来的矩形区域 [[0, 1], [-2, 3]] 的数值和是 2,且 2 是不超过 k 的最大数字(k = 2)。
示例2:
输入:matrix = [[2,2,-1]], k = 3
输出:3
提示:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-100 <= matrix[i][j] <= 100
-10^5 <= k <= 10^5
【分析】
-
太难了??,学到了很多,根据大神们的讨论,这应该是比较有代表的一类题,即二维矩形内部矩形区域值之和的相关问题。
-
不说了,上代码
// 在数组 arr 中,求不超过 k 的最大值 var dpmax = function(arr, k) { var rollSum = arr[0], rollMax = rollSum; // O(rows) for (var i = 1; i < arr.length; i++) { if (rollSum > 0) rollSum += arr[i]; else rollSum = arr[i]; if (rollSum > rollMax) rollMax = rollSum; } if (rollMax <= k) return rollMax; // O(rows ^ 2) var max = -1000001; for (var l = 0; l < arr.length; l++) { var sum = 0; for (var r = l; r < arr.length; r++) { sum += arr[r]; if (sum > max && sum <= k) max = sum; if (max == k) return k; // 尽量提前 } } return max; } var maxSumSubmatrix = function(matrix, k) { var rows = matrix.length, cols = matrix[0].length, max = -1000001; // O(cols ^ 2 * rows) for (var l = 0; l < cols; l++) { // 枚举左边界 var rowSum = new Array(rows).fill(0); // 左边界改变才算区域的重新开始 for (var r = l; r < cols; r++) { // 枚举右边界 for (var i = 0; i < rows; i++) { // 按每一行累计到 dp rowSum[i] += matrix[i][r]; } max = Math.max(max, dpmax(rowSum, k)); if (max == k) return k; // 尽量提前 } } return max; };
时间复杂度:\(O(cols^2*rows^2)\)
思路是
大神的数组滚动,大神们的题解已经写的很具体了,自己就签到一下吧。??
另一位,相同方法
官方题解思路差不多,差别在对一维数组求最大值时使用的有序集合,时间复杂度为\(O(log(n))\),总时间复杂度为\(O(m^2nlog(n))\)。
最后,自己不解的是,二维转一维时间复杂度为\(O(cols^2*rows^2)\)与暴力相同,为什么时间复杂度这么大……有人能告诉我一下嘛?
-
暴力(朴素dp
暴力解法即使使用了dp,但时间复杂度还是是硬核的\(O(m^2*n^2)\)。
var maxSumSubmatrix = function(matrix,k) { var rows = matrix.length, cols = matrix[0].length, max = -1000001; for (var i1 = 1; i1 <= rows; i1++) { for (var j1 = 1; j1 <= cols; j1++) { var dp = new Array(rows+1); for(var i=0;i
max) max = dp[i2][j2]; if(max == k) return max; } } } } return max; } -
前缀和+二分
前缀和也是这次学习知道的名词,前缀和指二维数组从(0,0)到(x,y)矩阵的元素和,因此也是一个二维数组。
题解见三叶姐姐题解。