Se nos da una matriz A de enteros positivos y dos enteros positivos L y R (L <= R).
Devuelve el número de subarreglos (contiguos, no vacíos) de modo que el valor del elemento de arreglo máximo en ese subarreglo sea al menos L y como máximo R.
Ejemplo :
Aporte:
A = [2, 1, 4, 3]
L = 2
R = 3
Salida: 3
Explicación: hay tres submatrices que cumplen los requisitos: [2], [2, 1], [3].
Solución Java
El límite de este problema es para cada elemento, no para la suma. Es fácil malinterpretar el problema, ya que hay muchas preguntas relacionadas con la suma.
Dada la matriz en la muestra [2,1,4,3], podemos convertirlo en una matriz [0,0,1,0], lo que significa que si el elemento está dentro del límite, es 0. Luego contamos el número de subarreglos.
Dada una matriz, el número total de submatriz sigue el siguiente patrón:
[0] -> 1 [0,0] -> 2 + 1 (single-element subarray + 2-element subarray) [0,0,0] -> 3 + 2 + 1 [0,0,0,0] -> 4 + 3 + 2 + 1
Por lo tanto, la solución es countBelowBoundary de R – countBelowBoundary of (L-1).
public int numSubarrayBoundedMax(int[] A, int L, int R) { return countBelowBoundary(A, R)-countBelowBoundary(A,L-1); } public int countBelowBoundary(int[] A, int bound){ int count = 0; int temp = 0; for(int a: A){ if(a<=bound){ temp = temp +1; count += temp; }else{ temp = 0; } } return count; } |
El tiempo es O (N) y el espacio es O (1).
