# 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?```

## 思路一：暴力循环

```    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;
}```

## 思路二：利用二分法思路进行优化

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

```    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>();
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);
}
}
}
}
return result;
}```

## 思路三：分治法

```    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 // 中位数是可以将数组分割为左右相等的数组，一个数将其分为左右相等...

• ### HDU 3450 Counting Sequences（线段树）

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

• ### 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...