Movatterモバイル変換


[0]ホーム

URL:


Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

Sign up
Appearance settings

Commit64e2758

Browse files
add 363
1 parent9330f0d commit64e2758

File tree

2 files changed

+57
-0
lines changed

2 files changed

+57
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -239,6 +239,7 @@ Your ideas/fixes/algorithms are more than welcome!
239239
|366|[Find Leaves of Binary Tree](https://leetcode.com/problems/find-leaves-of-binary-tree/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_366.java)| O(n)|O(h) | Medium| DFS
240240
|365|[Water and Jug Problem](https://leetcode.com/problems/water-and-jug-problem/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_365.java)| O(n)|O(1) | Medium| Math
241241
|364|[Nested List Weight Sum II](https://leetcode.com/problems/nested-list-weight-sum-ii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_364.java)| O(n)|O(h) | Medium| DFS
242+
|363|[Max Sum of Rectangle No Larger Than K](https://leetcode.com/problems/max-sum-of-rectangle-no-larger-than-k/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_363.java)| | | Hard| DP
242243
|362|[Design Hit Counter](https://leetcode.com/problems/design-hit-counter/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_362.java)| O(1) amortized|O(k) | Medium| Design
243244
|361|[Bomb Enemy](https://leetcode.com/problems/bomb-enemy/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_361.java)| O(?)|O(?)| Medium|
244245
|360|[Sort Transformed Array](https://leetcode.com/problems/sort-transformed-array/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_360.java)| O(n)|O(1) | Medium| Two Pointers, Math
Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
packagecom.fishercoder.solutions;
2+
3+
importjava.util.TreeSet;
4+
5+
/**
6+
* 363. Max Sum of Rectangle No Larger Than K
7+
*
8+
* Given a non-empty 2D matrix matrix and an integer k,
9+
* find the max sum of a rectangle in the matrix such that its sum is no larger than k.
10+
11+
Example:
12+
Given matrix = [
13+
[1, 0, 1],
14+
[0, -2, 3]
15+
]
16+
k = 2
17+
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).
18+
19+
Note:
20+
The rectangle inside the matrix must have an area > 0.
21+
What if the number of rows is much larger than the number of columns?
22+
*/
23+
publicclass_363 {
24+
/**reference: https://discuss.leetcode.com/topic/48854/java-binary-search-solution-time-complexity-min-m-n-2-max-m-n-log-max-m-n*/
25+
publicintmaxSumSubmatrix(int[][]matrix,intk) {
26+
introw =matrix.length;
27+
if (row ==0)return0;
28+
intcol =matrix[0].length;
29+
intm =Math.min(row,col);
30+
intn =Math.max(row,col);
31+
//indicating sum up in every row or every column
32+
booleancolIsBig =col >row;
33+
intres =Integer.MIN_VALUE;
34+
for (inti =0;i <m;i++) {
35+
int[]array =newint[n];
36+
// sum from row j to row i
37+
for (intj =i;j >=0;j--) {
38+
intval =0;
39+
TreeSet<Integer>set =newTreeSet<>();
40+
set.add(0);
41+
//traverse every column/row and sum up
42+
for (intp =0;p <n;p++) {
43+
array[p] =array[p] + (colIsBig ?matrix[j][p] :matrix[p][j]);
44+
val =val +array[p];
45+
//use TreeMap to binary search previous sum to get possible result
46+
Integersubres =set.ceiling(val -k);
47+
if (null !=subres) {
48+
res =Math.max(res,val -subres);
49+
}
50+
set.add(val);
51+
}
52+
}
53+
}
54+
returnres;
55+
}
56+
}

0 commit comments

Comments
 (0)

[8]ページ先頭

©2009-2025 Movatter.jp