LeetCode – Max Chunks para ordenar (Java)

Dado un arreglo arr que es una permutación de [0, 1, …, arr.length – 1], dividimos la matriz en cierto número de «fragmentos» (particiones) y clasificamos individualmente cada fragmento. Después de concatenarlos, el resultado es igual a la matriz ordenada.

¿Cuál es la mayor cantidad de trozos que pudimos haber hecho?

Por ejemplo, dado [2,0,1], el método devuelve 0, ya que solo puede haber un fragmento.

Análisis

La clave para resolver este problema es usar una pila para rastrear el fragmento existente. Cada fragmento está representado por un número mínimo y máximo. Cada fragmento es esencialmente un intervalo y el intervalo no puede superponerse.

Solución Java

public int maxChunksToSorted(int[] arr) {
    if(arr==null||arr.length==0){
        return 0;
    }
 
    // use [min,max] for each chunk
    Stack<int[]> stack = new Stack<int[]>();
 
    for(int i=0; i<arr.length; i++){
        int min=arr[i];
        int max=arr[i];
 
        while(!stack.isEmpty()){
            int[] top = stack.peek();
 
            if(arr[i] < top[1]){
                min=Math.min(top[0], min);
                max=Math.max(max, top[1]);
                stack.pop();
            }else{
                break;
            }
        }
 
        stack.push(new int[]{min,max});
    }
 
    return stack.size();
}

La complejidad del tiempo es O (n).