algorithms - Agua recogida entre torres



algorithm examples (16)

Hace poco me encontré con una pregunta de entrevista realizada por Amazon y no puedo encontrar un algoritmo optimizado para resolver esta pregunta:

Te dan una matriz de entrada cuyo elemento representa la altura de una línea de torres. El ancho de cada torre es 1. Comienza a llover. ¿Cuánta agua se recoge entre las torres?

Ejemplo

Input: [1,5,3,7,2] , Output: 2 units
Explanation: 2 units of water collected between towers of height 5 and 7

   *
   *
 *w*
 *w*
 ***
 ****
*****

Otro ejemplo

Input: [5,3,7,2,6,4,5,9,1,2] , Output: 14 units 
Explanation= 2 units of water collected between towers of height 5 and 7 +
             4 units of water collected between towers of height 7 and 6 + 
             1 units of water collected between towers of height 6 and 5 +
             2 units of water collected between towers of height 6 and 9 +
             4 units of water collected between towers of height 7 and 9 +
             1 units of water collected between towers of height 9 and 2.

Al principio pensé que esto podría ser resuelto por Stock-Span Problem ( http://www.geeksforgeeks.org/the-stock-span-problem/ ) pero estaba equivocado, así que sería genial si alguien puede pensar en un tiempo- algoritmo optimizado para esta pregunta.

https://ffff65535.com


Ninguna de las 17 respuestas ya publicadas son realmente óptimas en el tiempo.

Para un solo procesador, un barrido de 2 ( left->right , seguido de una suma de right->left ) es óptimo, como muchas personas han señalado, pero al usar muchos procesadores, es posible completar esta tarea en O (log n). ) hora. Hay muchas formas de hacerlo, por lo que explicaré una que sea bastante similar al algoritmo secuencial.

Árbol en caché máx. O (log n)

1: crea un árbol binario de todas las torres de modo que cada nodo contenga la altura de la torre más alta en cualquiera de sus elementos secundarios. Como las dos hojas de cualquier nodo se pueden calcular de forma independiente, esto se puede hacer en el tiempo O(log n) con n cpu.

2a: Entonces, para cada nodo en el árbol, comenzando en la raíz, deje que la hoja derecha tenga el valor max(left, self, right) . Esto creará el barrido monotónico de izquierda a derecha en el tiempo O(log n) , usando n cpu.

2b: para calcular el barrido de derecha a izquierda, hacemos el mismo procedimiento que antes. Comenzando con la raíz del árbol de máxima caché, deje que la hoja izquierda tenga el valor max(left, self, right) . Estos barridos de izquierda a derecha (2a) y de derecha a izquierda (2b) se pueden realizar en paralelo si lo desea. Ambos usan el árbol máximo en caché como entrada, y generan un árbol nuevo cada uno (o establece sus propios campos en el árbol original, si lo prefiere).

3: Entonces, para cada torre, la cantidad de agua es min(ltr, rtl) - towerHeight , donde ltr es el valor de esa torre en el barrido monotónico de izquierda a derecha que hicimos antes, es decir, la altura máxima de cualquier torre a la izquierda de nosotros (incluidos nosotros 1 ), y rtl es la misma para el barrido de derecha a izquierda.

4: Simplemente resuma esto usando un árbol en el tiempo O(log n) usando n cpu, y terminamos.

1 Si la torre actual es más alta que todas las torres a la izquierda de nosotros, o más alta que todas las torres a la derecha de nosotros, min(ltr, rtl) - towerHeight es cero.

Aquí hay otras dos formas de hacerlo .


Solución O (n) en Java, pase único

Otra implementación en Java, encontrar el agua recolectada en una sola pasada a través de la lista. Escaneé las otras respuestas pero no vi ninguna que obviamente estuviera usando mi solución.

  1. Encuentre el primer "pico" recorriendo la lista hasta que la altura de la torre deje de aumentar. Toda el agua antes de esto no se recogerá (escurrir hacia la izquierda).
  2. Para todas las torres posteriores:
    • Si la altura de la torre subsiguiente disminuye o permanece igual, agregue agua a una cubeta de "recolección potencial", igual a la diferencia entre la altura de la torre y la altura máxima de torre anterior.
    • Si la altura de la torre posterior aumenta, recogemos agua del cubo anterior (resta del cucharón de "recolección potencial" y lo agregamos al cucharón recogido) y también agregamos agua al cubo potencial igual a la diferencia entre la altura de la torre y el altura máxima de torre anterior.
    • Si encontramos una nueva torre máxima, entonces toda el "agua potencial" se mueve al cubo recogido y esta se convierte en la nueva altura máxima de la torre.

En el ejemplo anterior, con la entrada: [5,3,7,2,6,4,5,9,1,2], la solución funciona de la siguiente manera:

  • 5: Encuentra 5 como el primer pico
  • 3: Agrega 2 al cubo potencial (5-3)

    recogido = 0, potencial = 2

  • 7: Nuevo máximo, mueve toda el agua potencial al cubo recogido

    recogido = 2, potencial = 0

  • 2: Agrega 5 al cubo potencial (7-2)

    recogido = 2, potencial = 5

  • 6: mueve 4 al cubo recogido y agrega 1 al cubo potencial (6-2, 7-6)

    recogido = 6, potencial = 2

  • 4: agrega 2 al cubo potencial (6-4)

    recogido = 6, potencial = 4

  • 5: Mueve 1 al cubo recogido y agrega 2 al cubo potencial (5-4, 7-5)

    recogido = 7, potencial = 6

  • 9: Nuevo máximo, mueve toda el agua potencial al cubo recogido

    recogido = 13, potencial = 0

  • 1: Agrega 8 al cubo potencial (9-1)

    recogido = 13, potencial = 8

  • 2: Mueve 1 al cubo recogido y agrega 7 al cubo potencial (2-1, 9-2)

    recogido = 14, potencial = 15

Después de recorrer la lista una vez, se midió el agua recolectada.

public static int answer(int[] list) {
    int maxHeight = 0;
    int previousHeight = 0;
    int previousHeightIndex = 0;
    int coll = 0;
    int temp = 0;

    // find the first peak (all water before will not be collected)
    while(list[previousHeightIndex] > maxHeight) {
        maxHeight = list[previousHeightIndex];
        previousHeightIndex++;
        if(previousHeightIndex==list.length)            // in case of stairs (no water collected)
            return coll;
        else
            previousHeight = list[previousHeightIndex];
    }

    for(int i = previousHeightIndex; i<list.length; i++) {
        if(list[i] >= maxHeight) {      // collect all temp water
            coll += temp;
            temp = 0;
            maxHeight = list[i];        // new max height
        }
        else {
            temp += maxHeight - list[i];
            if(list[i] > previousHeight) {  // we went up... collect some water
                int collWater = (i-previousHeightIndex)*(list[i]-previousHeight);
                coll += collWater;
                temp -= collWater;
            }
        }

        // previousHeight only changes if consecutive towers are not same height
        if(list[i] != previousHeight) {
            previousHeight = list[i];
            previousHeightIndex = i;
        }
    }
    return coll;
}

Aquí está mi ir en Python. Estoy bastante seguro de que funciona pero no lo he probado.

Dos pasa a través de la lista (pero eliminando la lista cuando encuentra 'agua'):

respuesta def (alturas):

def accWater(lst,sumwater=0):
    x,takewater = 1,[]
    while x < len(lst):
        a,b = lst[x-1],lst[x]
        if takewater:
            if b < takewater[0]:
                takewater.append(b)
                x += 1
            else:
                sumwater += sum(takewater[0]- z for z in takewater)
                del lst[:x]
                x = 1
                takewater = []
        else:
            if b < a:
                takewater.extend([a,b])
                x += 1
            else:
                x += 1
    return [lst,sumwater]

heights, swater = accWater(heights)
x, allwater = accWater(heights[::-1],sumwater=swater)
return allwater

Aquí está mi opinión sobre el problema, utilizo un ciclo para ver si las torres anteriores son más grandes que la actual. Si es así, creo otro ciclo para verificar si las torres que vienen después del actual son más grandes o iguales a la torre anterior. Si ese es el caso, entonces solo agrego todas las diferencias de altura entre la torre anterior y todas las otras torres. Si no, y si mi bucle alcanza mi último objeto, simplemente invierto la matriz para que la torre anterior se convierta en mi última torre y llame mi método de forma recursiva. De esa manera, estoy seguro de encontrar una torre más grande que mi nueva torre anterior y encontraré la cantidad correcta de agua recolectada.

public class towers {
    public static int waterLevel(int[] i) {
        int totalLevel = 0;

        for (int j = 1; j < i.length - 1; j++) {
            if (i[j - 1] > i[j]) {
                for (int k = j; k < i.length; k++) {
                    if (i[k] >= i[j  - 1]) {
                        for (int l = j; l < k; l++) { 
                            totalLevel += (i[j - 1] - i[l]);
                        }

                        j = k;
                        break;
                    }  

                    if (k == i.length - 1) {
                        int[] copy = Arrays.copyOfRange(i, j - 1, k + 1);
                        int[] revcopy = reverse(copy);
                        totalLevel += waterLevel(revcopy);
                    }
                }
            }
        }

        return totalLevel;
    }

    public static int[] reverse(int[] i) {
        for (int j = 0; j < i.length / 2; j++) {
            int temp = i[j];
            i[j] = i[i.length - j - 1];
            i[i.length - j - 1] = temp;
        }

        return i;
    }

    public static void main(String[] args) {
        System.out.println(waterLevel(new int[] {1, 6, 3, 2, 2, 6}));
    }
}

Aquí hay una solución eficiente en Haskell

rainfall :: [Int] -> Int
rainfall xs = sum (zipWith (-) mins xs)
    where mins = zipWith min maxl maxr
          maxl = scanl1 max xs
          maxr = scanr1 max xs

usa el mismo algoritmo de escaneo de dos pasadas mencionado en las otras respuestas.


Aquí hay una solución en Groovy en dos pases.

assert waterCollected([1, 5, 3, 7, 2]) == 2
assert waterCollected([5, 3, 7, 2, 6, 4, 5, 9, 1, 2]) == 14
assert waterCollected([5, 5, 5, 5]) == 0
assert waterCollected([5, 6, 7, 8]) == 0
assert waterCollected([8, 7, 7, 6]) == 0
assert waterCollected([6, 7, 10, 7, 6]) == 0

def waterCollected(towers) {
    int size = towers.size()
    if (size < 3) return 0

    int left = towers[0]
    int right = towers[towers.size() - 1]

    def highestToTheLeft = []
    def highestToTheRight = [null] * size

    for (int i = 1; i < size; i++) {

        // Track highest tower to the left
        if (towers[i] < left) {
            highestToTheLeft[i] = left
        } else {
            left = towers[i]
        }

        // Track highest tower to the right
        if (towers[size - 1 - i] < right) {
            highestToTheRight[size - 1 - i] = right
        } else {
            right = towers[size - 1 - i]
        }
    }

    int water = 0
    for (int i = 0; i < size; i++) {
        if (highestToTheLeft[i] && highestToTheRight[i]) {
            int minHighest = highestToTheLeft[i] < highestToTheRight[i] ? highestToTheLeft[i] : highestToTheRight[i]
            water += minHighest - towers[i]
        }
    }

    return water
}

Aquí el mismo fragmento con un compilador en línea: https://groovy-playground.appspot.com/#?load=3b1d964bfd66dc623c89


Aquí hay una solución más escrita en Scala

def find(a: Array[Int]): Int = {
  var count, left, right = 0

  while (left < a.length - 1) {
    right = a.length - 1
    for (j <- a.length - 1 until left by -1) {
      if (a(j) > a(right)) right = j
    }

    if (right - left > 1) {
      for (k <- left + 1 until right) count += math.min(a(left), a(right)) - a(k)
      left = right
    } else left += 1
  }

  count
}

Consulte este sitio web para obtener el código, es realmente simple y simple http://learningarsenal.info/index.php/2015/08/21/amount-of-rain-water-collected-between-towers/

Entrada: [5,3,7,2,6,4,5,9,1,2], Salida: 14 unidades

Explicación

Cada torre puede contener agua hasta un nivel de la altura más pequeña entre la torre más alta a la izquierda y la torre más alta a la derecha.

Por lo tanto, necesitamos calcular la torre más alta a la izquierda en cada torre, y también para el lado derecho.

Aquí necesitaremos dos matrices adicionales para mantener la altura de la torre más alta a la izquierda en cualquier torre, digamos, int leftMax [] y del mismo modo para el lado derecho, decir int rightMax [].

PASO 1

Hacemos un pase a la izquierda de la matriz dada (es decir, int torre []), y mantendremos un máximo temporal (digamos int tempMax) de modo que en cada iteración la altura de cada torre se comparará con tempMax, y si la altura de la torre actual es menor que tempMax, entonces tempMax se configurará como la torre más alta a la izquierda, de lo contrario la altura de la torre actual se asignará como la torre más alta a la izquierda y tempMax se actualizará con la altura actual de la torre,

PASO 2

Seguiremos el procedimiento anterior solo como se discutió en el PASO-1 para calcular la torre más alta a la derecha PERO esta vez haciendo una pasada desde el lado derecho.

PASO 3

La cantidad de agua que puede contener cada torre es:

(altura mínima entre la torre más alta a la derecha y la torre más a la izquierda) - (altura de la torre)


La primera y la última barra de la lista no pueden atrapar agua. Para las torres restantes, pueden atrapar agua cuando hay alturas máximas a la izquierda y a la derecha.

la acumulación de agua es: max (min (max_left, max_right) - current_height, 0)

Iterando desde la izquierda, si sabemos que hay un max_right que es mayor, min (max_left, max_right) se convertirá en max_left. Por lo tanto, la acumulación de agua se simplifica como: max (max_left - current_height, 0) Mismo patrón cuando se considera desde el lado derecho.

De la información anterior, podemos escribir un algoritmo O (N) time y O (1) space de la siguiente manera (en Python):

def trap_water(A):

     water = 0
     left, right = 1, len(A)-1
     max_left, max_right = A[0], A[len(A)-1]

     while left <= right:
         if A[left] <= A[right]:
             max_left = max(A[left], max_left)
             water += max(max_left - A[left], 0)
             left += 1
         else:
             max_right = max(A[right], max_right)
             water += max(max_right - A[right], 0)
             right -= 1

     return water

Mi fea solución transversal única

def water_collection(buildings):
  valleyFlag = False
  water = 0
  pool = []
  for i, building in enumerate(buildings):
    if(i == 0):
      lastHill = building
    else:
      if lastHill <= building or i == len(buildings)-1:
        minHill = min(building, lastHill)
        print("Hill {} to Hill {}".format(lastHill, building))
        summ = 0
        for drop in pool:
          summ += minHill - drop
          water += minHill - drop
        print("Collected sum {}".format(summ))
        pool = []
        valleyFlag = False
        lastHill = building
      elif lastHill > building and valleyFlag == False:
        pool.append(building)
        valleyFlag = True
      elif lastHill > building and valleyFlag == True:
        pool.append(building)

  print(water)

Programa de JavaScript para encontrar agua total de la tienda:

let buildingHeights = [6, 1, 3, 5, 9, 2, 8];
/*
 * TOTAL store water
 * */
let max = (n1, n2) => {
    return n1 > n2 ? n1 : n2;
};
let min = (n1, n2) => {
    return n1 > n2 ? n2 : n1;
};

let maxHeightFromLeft = {}, maxHeightFromRight = {};
for (let i = 0; i < buildingHeights.length; i++) {
    maxHeightFromLeft[i] = max(buildingHeights[i], (i != 0) ? maxHeightFromLeft[i - 1] : 0);
}
for (let i = buildingHeights.length - 1; i >= 0; i--) {
    maxHeightFromRight[i] = max(buildingHeights[i], i < (buildingHeights.length - 1) ? maxHeightFromRight[i + 1] : 0);
}
let totalStorage = 0;
for (let i = 0; i < buildingHeights.length; i++) {
    totalStorage += min(maxHeightFromLeft[i], maxHeightFromRight[i]) - buildingHeights[i];
}
console.log(totalStorage);

Puede atravesar primero de izquierda a derecha y calcular el agua acumulada para los casos en que hay un edificio más pequeño a la izquierda y uno más grande a la derecha. Tendría que restar el área de los edificios que están entre estos dos edificios y son más pequeños que el izquierdo.

Similar sería el caso de derecha a izquierda.

Aquí está el código de izquierda a derecha. He cargado este problema en leetcode online judge usando este enfoque.

Encuentro este enfoque mucho más intuitivo que la solución estándar que está presente en todas partes (calculando el edificio más grande a la derecha e izquierda para cada i).

int sum=0, finalAns=0;
    idx=0;
    while(a[idx]==0 && idx < n)
        idx++;
    for(int i=idx+1;i<n;i++){

        while(a[i] < a[idx] && i<n){
            sum += a[i];
            i++;
        }
        if(i==n)
            break;
        jdx=i;
        int area = a[idx] * (jdx-idx-1);
        area -= sum;
        finalAns += area;

        idx=jdx;
        sum=0;
    }

La complejidad temporal de este enfoque es O (n), ya que atraviesa la matriz dos veces de forma lineal. La complejidad del espacio sería O (1).


Solución legible de Python:

def water_collected(heights):
    water_collected = 0
    left_height = []
    right_height = []

    temp_max = heights[0]
    for height in heights:
        if (height > temp_max):
            temp_max = height
        left_height.append(temp_max)

    temp_max = heights[-1]
    for height in reversed(heights):
        if (height > temp_max):
            temp_max = height
        right_height.insert(0, temp_max)

    for i, height in enumerate(heights):
        water_collected += min(left_height[i], right_height[i]) - height
    return water_collected

Tengo una solución que solo requiere un recorrido único de izquierda a derecha.

def standing_water(heights):

    if len(heights) < 3:
        return 0

    i = 0   # index used to iterate from left to right
    w = 0   # accumulator for the total amount of water

    while i < len(heights) - 1:

        target = i + 1
        for j in range(i + 1, len(heights)):

            if heights[j] >= heights[i]:
                target = j
                break

            if heights[j] > heights[target]:
                target = j

        if target == i:
            return w

        surface = min(heights[i], heights[target])

        i += 1

        while i < target:
            w += surface - heights[i]
            i += 1

    return w

Una solución intuitiva para este problema es aquella en la que se vincula el problema y se llena el agua en función de la altura de los límites izquierdo y derecho.

Mi solución:

  • Comience por la izquierda, estableciendo ambos límites para ser el 0 ° índice.
  • Comprueba y observa si hay algún tipo de trayectoria (si caminas sobre estas torres, ¿alguna vez bajarás y luego volverás a subir?) Si ese es el caso, entonces has encontrado un límite correcto.
  • Ahora regrese y llene el agua en consecuencia (simplemente agregué el agua a los valores de la matriz, ya que hace que el código sea un poco más limpio, pero obviamente no es necesario).
  • La línea de golpe: si la altura de la torre de límite izquierdo es mayor que la altura de la torre de límite derecho que la que necesita para incrementar el límite correcto. La razón es porque es posible que te topes con una torre más alta y necesites llenar un poco más de agua. Sin embargo, si la torre derecha es más alta que la izquierda, entonces no se puede agregar más agua en su sub-problema actual. Por lo tanto, mueves tu límite izquierdo al límite derecho y continúas.

Aquí hay una implementación en C #:

        int[] towers = {1,5,3,7,2};

        int currentMinimum = towers[0];

        bool rightBoundFound = false;

        int i = 0;
        int leftBoundIndex = 0;
        int rightBoundIndex = 0;

        int waterAdded = 0;

        while(i < towers.Length - 1)
        {

            currentMinimum = towers[i];

            if(towers[i] < currentMinimum)
            {
                currentMinimum = towers[i];
            }

            if(towers[i + 1] > towers[i])
            {
                rightBoundFound = true;
                rightBoundIndex = i + 1;
            }

            if (rightBoundFound)
            {

                for(int j = leftBoundIndex + 1; j < rightBoundIndex; j++)
                {

                    int difference = 0;

                    if(towers[leftBoundIndex] < towers[rightBoundIndex])
                    {
                        difference = towers[leftBoundIndex] - towers[j];
                    }
                    else if(towers[leftBoundIndex] > towers[rightBoundIndex])
                    {
                        difference = towers[rightBoundIndex] - towers[j];
                    }
                    else
                    {
                        difference = towers[rightBoundIndex] - towers[j];
                    }

                    towers[j] += difference;
                    waterAdded += difference;

                }

                if (towers[leftBoundIndex] > towers[rightBoundIndex])
                {
                    i = leftBoundIndex - 1;
                }
                else if (towers[rightBoundIndex] > towers[leftBoundIndex])
                {
                    leftBoundIndex = rightBoundIndex;
                    i = rightBoundIndex - 1;
                }
                else
                {
                    leftBoundIndex = rightBoundIndex;
                    i = rightBoundIndex - 1;
                }
                rightBoundFound = false;

            }

            i++;

        }

No tengo dudas de que hay más soluciones óptimas. Actualmente estoy trabajando en una optimización de un solo pase. También hay una implementación muy ordenada de pila de este problema, y ​​utiliza una idea similar de delimitación .


Una vez que el agua haya caído, cada posición se llenará a un nivel igual a la más pequeña de la torre más alta a la izquierda y la torre más alta a la derecha.

Encuentre, mediante un barrido hacia la derecha, la torre más alta a la izquierda de cada posición. Luego encuentre, mediante un escaneo hacia la izquierda, la torre más alta a la derecha de cada posición. Luego tome el mínimo en cada posición y agréguelas todas.

Algo como esto debería funcionar:

int tow[N]; // nonnegative tower heights
int hl[N] = {0}, hr[N] = {0}; // highest-left and highest-right
for (int i = 0; i < n; i++) hl[i] = max(tow[i], (i!=0)?hl[i-1]:0);
for (int i = n-1; i >= 0; i--) hr[i] = max(tow[i],i<(n-1) ? hr[i+1]:0);
int ans = 0;
for (int i = 0; i < n; i++) ans += min(hl[i], hr[i]) - tow[i];




algorithm