2022-01-20： 矩形区域不超过 K 的最大数值和。 给你一个 m x n 的矩阵 matrix 和一个整数 k

2022-01-20： 矩形区域不超过 K 的最大数值和。 给你一个 m x n 的矩阵 matrix 和一个整数 k ，找出并返回矩阵内部矩形区域的不超过 k 的最大数值和。 题目数据保证总会存在一个数值和不超过 k 的矩形区域。 力扣363。

答案2022-01-20：

有序表。前缀和。压缩数组。

代码用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
}

执行结果如下：

左神java代码