Leetcode: Trapping rain water en C#.

En este post te voy a explicar como resolver el problema: Trapping rain water, de la plataforma Leetcode.

El algoritmo del problema: Trapping rain water, es sencillo. Dado un arreglo de números, que representan elevaciones; debes determinar la cantidad de agua que pueden almacenar. Para eso, necesitas saber que si la elevación en cuestión genera un valle.

Por ejemplo: [1, 0, 1] generan un valle, en cambio [0, 1, 1], no. Necesitas ser capaz de poder identificar las paredes de un valle para calcular la cantidad de agua. Si la pared izquierda, y la pared derecha son mayores que la elevación en cuestión, entonces, se puede calcular la cantidad de lluvia.

Hasta a aquí no hay problema, para el caso más basicos. El problema que te surgirá son los casos extremos como los valles y montañas. Aparte de conocer las paredes inmediatas, necesitas saber si las paredes en cuestión son las más grandes hasta ahora. En el siguiente caso: [3,0,2,0,3], si solo usas las paredes inmediatas para calcular la lluvia vas a producir un resultado de 4, en cambio, si usas las paredes más grandes a la derecha y a la izquierda el resultado cambia. De un resultado de 4, obtienes 7.

¿Como solucionar el problema?

Necesitas recorrer el algoritmo de izquierda a derecha y de derecha a izquierda al mismo tiempo. En cada iteración vas a preguntar si el lado izquierdo es el valor máximo, y también, si el otro lado es el mayor. Una vez que estableces que el valor es el mayor posible, calculas el monto de agua.

En el siguiente ejemplo, dado el arreglo [2,3,0,2,0,3,2]

1. Arr: [2,3,0,1,0,3,2], MaxL: 2, MaxR: 2. ¿Puede calcular lluvia?, No.
2. Arr: [_,3,0,1,0,3,_], MaxL: 3, MaxR: 3. ¿Puede calcular lluvia?, No.
3. Arr: [_,_,_,1,_,_,_], MaxL: 3, MaxR: 3. ¿Puede calcular lluvia?, Sí. Lluvia = 3 + 3
4. Arr: [_,_,_,_,_,_,_], MaxL: 3, MaxR: 3. ¿Puede calcular lluvia?, Sí. Lluvia = 3 + 3 + 2

Solución.

• Acerca de
• Últimas entradas

Gustavo Sánchez

Especialista en escribir software de calidad. en Happy Devops

Soy especialista en escribir software de calidad. Mediante el uso de marcos de trabajo, técnicas y automatización de procesos he podido reducir los costes operativos de los sistemas de la empresa. Sistemas confiables y adaptables producen clientes felices.

Últimas entradas de Gustavo Sánchez (ver todo)

• NVL in SQL Server - 2023-11-01
• ¿Que es Cake Build? - 2023-02-22
• #How to fix error: MSB4019: The imported project «Microsoft.Data.Tools.Schema.SqlTasks.targets» was not found - 2023-02-20