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: Given matrix = [ [1, 0, 1], [0, -2, 3] ] k = 2 The answer is 2. Because the sum of rectangle [[0, 1], [-2, 3]] is 2 and 2 is the max number no larger than k (k = 2).
這道題目其實(shí)是兩個(gè)子問(wèn)題的結(jié)合，解決了這兩個(gè)子問(wèn)題可以很容易的解決此題。
也就是在一個(gè)二維數(shù)組中，尋找一個(gè)最大直方和。暴力解法就是取矩形對(duì)角兩點(diǎn)的元素，進(jìn)行遍歷求和，復(fù)雜度是O(MNMN). 暴力循環(huán)可以通過(guò)動(dòng)態(tài)規(guī)劃進(jìn)行優(yōu)化，用一個(gè)數(shù)組存儲(chǔ)當(dāng)前矩形的累計(jì)和。如下圖： 
綠色數(shù)組記錄了藍(lán)色區(qū)域的和，通過(guò)數(shù)組記錄下之前的值避免了重復(fù)計(jì)算。在綠色數(shù)組中，尋找不大于k的最大和連續(xù)子數(shù)組，相當(dāng)于在確定了藍(lán)色矩形左右邊界的情況下，通過(guò)修改上下邊界尋找最大和矩形。同樣，全遍歷二維數(shù)組每一列：
。。。 
全遍歷后，則找出了全部矩形。
如果不包含不大于k的限制，那么就是一個(gè)普通的dp問(wèn)題。類似于leetcode上這道題目： stock問(wèn)題。 對(duì)于不大k的，則是構(gòu)建一個(gè)二插查找樹(shù)BST，java中對(duì)應(yīng)可以使用TreeMap。對(duì)于一個(gè)數(shù)組，子數(shù)組(i,j]的和可以通過(guò)sum[0,j] - sum[0,i]來(lái)求出。在遍歷這個(gè)子數(shù)組的時(shí)候計(jì)算出當(dāng)前的累加和 rightSum并加入到BST中，記leftSum為之前存儲(chǔ)在BST中的數(shù)，因?yàn)橐?rightSum - leftSum <=k，則有l(wèi)eftSum >= rightSum - k，同時(shí)leftSum越小，求和值rightSum-leftSum越大。所以去BST中找大于等于 rightSum-k的最小數(shù)leftSum，并更新全局最優(yōu)，即得結(jié)果。
最終代碼如下：
public class Solution { public int maxSumSubmatrix(int[][] matrix, int k) { int row = matrix.length; int col = matrix[0].length; int res = Integer.MIN_VALUE; //子問(wèn)題1，三個(gè)for循環(huán)全遍歷。 for (int i = 0;i < col;i++) { int[] arr = new int[row]; for (int j = i;j < col;j++) { int rightSum = 0; TreeSet<Integer> sums = new TreeSet<>(); sums.add(0); for (int l = 0; l < row;l++) { arr[l] += matrix[l][j]; //子問(wèn)題二，尋找leftSum。計(jì)算最大和連續(xù)子數(shù)組 rightSum += arr[l]; Integer leftSum = sums.ceiling(rightSum - k); if (leftSum!=null) res = Math.max(res, rightSum - leftSum); sums.add(rightSum); } } } return res; }}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
