LeetCode – Suma máxima de rectángulo no mayor que K (Java)

Dada una matriz de matriz 2D no vacía y un número entero k, encuentre la suma máxima de un rectángulo en la matriz tal que su suma no sea mayor que k.

Ejemplo:

Given matrix = [
  [1,  0, 1],
  [0, -2, 3]
]
k = 2

La respuesta es 2. Porque la suma del rectángulo [[0, 1], [-2, 3]]es 2 y 2 es el número máximo no mayor que k (k = 2).

Nota:
El rectángulo dentro de la matriz debe tener un área> 0.
¿Qué pasa si el número de filas es mucho mayor que el número de columnas?

Análisis

Podemos resolver este problema comparando cada submatriz. Este método es trivial y necesitamos una mejor solución. La clave para la solución óptima es usar un conjunto de árboles para calcular la suma máxima de subarreglos cerca de k.

Solución Java 1

public int maxSumSubmatrix(int[][] matrix, int k) {
    if(matrix==null||matrix.length==0||matrix[0].length==0)
        return 0;
 
    int m=matrix.length;
    int n=matrix[0].length;
 
    int result = Integer.MIN_VALUE;
 
    for(int c1=0; c1<n; c1++){
        int[] each = new int[m];
        for(int c2=c1; c2>=0; c2--){
 
            for(int r=0; r<m; r++){
                each[r]+=matrix[r][c2];   
            }
 
            result = Math.max(result, getLargestSumCloseToK(each, k));
        }
    }
 
    return result;
}
 
public int getLargestSumCloseToK(int[] arr, int k){
    int sum=0;
    TreeSet<Integer> set = new TreeSet<Integer>();
    int result=Integer.MIN_VALUE;
    set.add(0);
 
    for(int i=0; i<arr.length; i++){
        sum=sum+arr[i];
 
        Integer ceiling = set.ceiling(sum-k);
        if(ceiling!=null){
            result = Math.max(result, sum-ceiling);        
        }
 
        set.add(sum);
    }
 
    return result;
}

LeetCode - Combinaciones de letras de un número de teléfono (Java)

La complejidad del tiempo es O (n * n * m * log (m)). Si m es mayor que n, esta solución está bien. Sin embargo, si m es menor que n, entonces esta solución no es óptima. En este caso, deberíamos invertir la fila y la columna, como la Solución 2.

Solución Java 2

public int maxSumSubmatrix(int[][] matrix, int k) {
    if(matrix==null||matrix.length==0||matrix[0].length==0)
        return 0;
 
    int row=matrix.length;
    int col=matrix[0].length;
 
    int m = Math.max(row, col);
    int n = Math.min(row, col);
    boolean isRowLarger = false;
    if(row>col)
        isRowLarger=true;
 
    int result = Integer.MIN_VALUE;
 
    for(int c1=0; c1<n; c1++){
 
        int[] each = new int[m];
        for(int c2=c1; c2>=0; c2--){
 
            for(int r=0; r<m; r++){
                each[r]+=isRowLarger?matrix[r][c2]:matrix[c2][r];   
            }
 
            result = Math.max(result, getLargestSumCloseToK(each, k));
        }
    }
 
    return result;
}
 
public int getLargestSumCloseToK(int[] arr, int k){
    int sum=0;
    TreeSet<Integer> set = new TreeSet<Integer>();
    int result=Integer.MIN_VALUE;
    set.add(0);
 
    for(int i=0; i<arr.length; i++){
        sum=sum+arr[i];
 
        Integer ceiling = set.ceiling(sum-k);
        if(ceiling!=null){
            result = Math.max(result, sum-ceiling);        
        }
 
        set.add(sum);
    }
 
    return result;
}

Artículos Relacionados:

Por Programación.Click

Deja una respuesta Cancelar la respuesta