矩形区域不超过 K 的最大数值和。
给你一个 m x n 的矩阵 matrix 和一个整数 k ，找出并返回矩阵内部矩形区域的不超过 k 的最大数值和。
题目数据保证总会存在一个数值和不超过 k 的矩形区域。
力扣363。
有序表。前缀和。压缩数组。
代码用golang编写。代码如下：
package main
import (
"fmt"
"math"
"sort"
)
func main() {
matrix := [][]int{{1, 0, 1}, {0, -2, 3}}
k := 2
ret := maxSumSubmatrix(matrix, k)
fmt.Println(ret)
}
func nearK(arr []int, k int) int {
if len(arr) == 0 {
return math.MinInt64
}
//TreeSet<Integer> set = new TreeSet<>();
set := make(map[int]struct{})
//set.add(0);
set[0] = struct{}{}
ans := math.MaxInt64
sum := 0
for i := 0; i < len(arr); i++ {
// 讨论子数组必须以i位置结尾，最接近k的累加和是多少？
sum += arr[i]
// 找之前哪个前缀和 >= sum - k 且最接近
// 有序表中，ceiling(x) 返回>=x且最接近的！
// 有序表中，floor(x) 返回<=x且最接近的！
find, ok := ceiling(set, sum-k)
if ok {
curAns := sum - find
ans = getMax(ans, curAns)
}
set[sum] = struct{}{}
}
return ans
}
func maxSumSubmatrix(matrix [][]int, k int) int {
if len(matrix) == 0 || len(matrix[0]) == 0 {
return 0
}
if len(matrix) > len(matrix[0]) {
matrix = rotate(matrix)
}
row := len(matrix)
col := len(matrix[0])
res := math.MinInt64
sumSet := make(map[int]struct{})
for s := 0; s < row; s++ {
colSum := make([]int, col)
for e := s; e < row; e++ {
// s ~ e 这些行 选的子矩阵必须包含、且只包含s行~e行的数据
// 0 ~ 0 0 ~ 1 0 ~ 2 。。。
// 1 ~ 2 1 ~ 2 1 ~ 3 。。。
sumSet[0] = struct{}{}
rowSum := 0
for c := 0; c < col; c++ {
colSum[c] += matrix[e][c]
rowSum += colSum[c]
it, ok := ceiling(sumSet, rowSum-k)
if ok {
res = getMax(res, rowSum-it)
}
sumSet[rowSum] = struct{}{}
}
//sumSet.clear();
sumSet = make(map[int]struct{})
}
}
return res
}
func rotate(matrix [][]int) [][]int {
N := len(matrix)
M := len(matrix[0])
//int[][] r = new int[M][N];
r := make([][]int, M)
for i := 0; i < M; i++ {
r[i] = make([]int, N)
}
for i := 0; i < N; i++ {
for j := 0; j < M; j++ {
r[j][i] = matrix[i][j]
}
}
return r
}
func getMax(a, b int) int {
if a > b {
return a
} else {
return b
}
}
func ceiling(set map[int]struct{}, v int) (res int, ok bool) {
arr := make([]int, 0)
for k, _ := range set {
arr = append(arr, k)
}
sort.Ints(arr)
index := NearestIndex(arr, v)
if index == -1 {
return
} else {
ok = true
res = arr[index]
return
}
}
// 在arr上，找满足>=value的最左位置
func NearestIndex(arr []int, v int) int {
L := 0
R := len(arr) - 1
index := -1 // 记录最左的对号
for L <= R {
mid := L + (R-L)>>1
if arr[mid] >= v {
index = mid
R = mid - 1
} else {
L = mid + 1
}
}
return index
}执行结果如下：
