Dada una array de enteros que representa las alturas de N edificios, la tarea es eliminar N-2 edificios de modo que el agua que pueda quedar atrapada entre los dos edificios restantes sea máxima. Tenga en cuenta que el agua total atrapada entre dos edificios es un espacio entre ellos (la cantidad de edificios eliminados) multiplicado por la altura del edificio más pequeño.
Ejemplos:
Entrada: arr[] = {1, 3, 4}
Salida: 1
Tenemos que calcular el agua máxima que se puede almacenar entre 2 edificios cualesquiera.
Agua entre los edificios de altura 1 y altura 3 = 0.
Agua entre los edificios de altura 1 y altura 4 = 1.
Agua entre los edificios de altura 3 y altura 4 = 0.
Por tanto, el máximo de todos los casos es 1.Entrada: arr[] = {2, 1, 3, 4, 6, 5}
Salida: 8
Eliminamos los 4 edificios del medio y obtenemos el agua total almacenada como 2 * 4 = 8
Enfoque ingenuo:
verifique todos los pares posibles y el par que pueda contener el máximo de agua será la respuesta.
El agua almacenada entre dos edificios de altura h 1 y h 2 sería igual a:
minimum(h1, h2)*(distance between the buildings-1)
Nuestra tarea es maximizar este valor para cada par.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Return the maximum water that can be stored
int maxWater(int height[], int n)
{
int maximum = 0;
// Check all possible pairs of buildings
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
int current = (min(height[i],
height[j])
* (j - i - 1));
// Maximum so far
maximum = max(maximum, current);
}
}
return maximum;
}
// Driver code
int main()
{
int height[] = { 2, 1, 3, 4, 6, 5 };
int n = sizeof(height) / sizeof(height[0]);
cout << maxWater(height, n);
return 0;
}
Java
// Java implementation of the above approach
class GFG {
// Return the maximum water that can be stored
static int maxWater(int height[], int n)
{
int max = 0;
// Check all possible pairs of buildings
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
int current = (Math.min(height[i],
height[j])
* (j - i - 1));
// Maximum so far
max = Math.max(max, current);
}
}
return max;
}
// Driver code
public static void main(String[] args)
{
int height[] = { 2, 1, 3, 4, 6, 5 };
int n = height.length;
System.out.print(maxWater(height, n));
}
}
Python3
# Python3 implementation of the above approach # Return the maximum water # that can be stored def maxWater(height, n) : maximum = 0 # Check all possible pairs of buildings for i in range(n - 1) : for j in range(i + 1, n) : current = min(height[i], height[j]) * (j - i - 1) # Maximum so far maximum = max(maximum, current) return maximum # Driver code if __name__ == "__main__" : height = [ 2, 1, 3, 4, 6, 5 ] n = len(height) print(maxWater(height, n))
C#
// C# implementation of the above approach
using System;
class GFG {
// Return the maximum water that can be stored
static int maxWater(int[] height, int n)
{
int max = 0;
// Check all possible pairs of buildings
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
int current = (Math.Min(height[i],
height[j])
* (j - i - 1));
// Maximum so far
max = Math.Max(max, current);
}
}
return max;
}
// Driver code
static public void Main()
{
int[] height = { 2, 1, 3, 4, 6, 5 };
int n = height.Length;
Console.WriteLine(maxWater(height, n));
}
}
Javascript
<script>
// Javascript implementation of the above approach
// Return the maximum water that can be stored
function maxWater( height, n)
{
let maximum = 0;
// Check all possible pairs of buildings
for (let i = 0; i < n - 1; i++) {
for (let j = i + 1; j < n; j++) {
let current = (Math.min(height[i],
height[j])
* (j - i - 1));
// Maximum so far
maximum = Math.max(maximum, current);
}
}
return maximum;
}
// Driver program
let height = [ 2, 1, 3, 4, 6, 5 ];
let n = height.length;
document.write(maxWater(height, n));
</script>
Producción:
8
Complejidad de tiempo: O(N*N)
Enfoque eficiente:
- Ordene la array de acuerdo con la altura creciente sin afectar los índices originales, es decir, haga pares de (elemento, índice).
- Luego, para cada elemento, suponga que es el edificio con la altura mínima entre los dos edificios requeridos, entonces la altura del agua requerida será igual a la altura del edificio elegido y el ancho será igual a la diferencia de índice entre el edificio elegido y el edificio que se encuentra.
- Para elegir el otro edificio que maximiza el agua, el otro edificio debe estar lo más lejos posible y debe tener una altura mayor en comparación con el edificio elegido actualmente.
- Ahora, el problema se reduce a encontrar los índices mínimo y máximo a la derecha para cada edificio en la array ordenada.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include<bits/stdc++.h>
using namespace std;
bool compareTo(pair<int, int> p1,
pair<int, int> p2)
{
return p1.second < p2.second;
}
// Return the maximum water that
// can be stored
int maxWater(int height[], int n)
{
// Make pairs with indices
pair<int, int> pairs[n];
for(int i = 0; i < n; i++)
pairs[i] = make_pair(i, height[i]);
// Sort array based on heights
sort(pairs, pairs + n, compareTo);
// To store the min and max index so far
// from the right
int minIndSoFar = pairs[n - 1].first;
int maxIndSoFar = pairs[n - 1].first;
int maxi = 0;
for(int i = n - 2; i >= 0; i--)
{
// Current building paired with
// the building greater in height
// and on the extreme left
int left = 0;
if (minIndSoFar < pairs[i].first)
{
left = (pairs[i].second *
(pairs[i].first -
minIndSoFar - 1));
}
// Current building paired with
// the building greater in height
// and on the extreme right
int right = 0;
if (maxIndSoFar > pairs[i].first)
{
right = (pairs[i].second *
(maxIndSoFar -
pairs[i].first - 1));
}
// Maximum so far
maxi = max(left, max(right, maxi));
// Update the maximum and minimum so far
minIndSoFar = min(minIndSoFar,
pairs[i].first);
maxIndSoFar = max(maxIndSoFar,
pairs[i].first);
}
return maxi;
}
// Driver code
int main( )
{
int height[] = { 2, 1, 3, 4, 6, 5 };
int n = sizeof(height) / sizeof(height[0]);
cout << maxWater(height, n);
}
Java
// Java implementation of the above approach
import java.util.Arrays;
// Class to store the pairs
class Pair implements Comparable<Pair> {
int ind, val;
Pair(int ind, int val)
{
this.ind = ind;
this.val = val;
}
@Override
public int compareTo(Pair o)
{
if (this.val > o.val)
return 1;
return -1;
}
}
class GFG {
// Return the maximum water that can be stored
static int maxWater(int height[], int n)
{
// Make pairs with indices
Pair pairs[] = new Pair[n];
for (int i = 0; i < n; i++)
pairs[i] = new Pair(i, height[i]);
// Sort array based on heights
Arrays.sort(pairs);
// To store the min and max index so far
// from the right
int minIndSoFar = pairs[n - 1].ind;
int maxIndSoFar = pairs[n - 1].ind;
int max = 0;
for (int i = n - 2; i >= 0; i--) {
// Current building paired with the building
// greater in height and on the extreme left
int left = 0;
if (minIndSoFar < pairs[i].ind) {
left = (pairs[i].val * (pairs[i].ind - minIndSoFar - 1));
}
// Current building paired with the building
// greater in height and on the extreme right
int right = 0;
if (maxIndSoFar > pairs[i].ind) {
right = (pairs[i].val * (maxIndSoFar - pairs[i].ind - 1));
}
// Maximum so far
max = Math.max(left, Math.max(right, max));
// Update the maximum and minimum so far
minIndSoFar = Math.min(minIndSoFar,
pairs[i].ind);
maxIndSoFar = Math.max(maxIndSoFar,
pairs[i].ind);
}
return max;
}
// Driver code
public static void main(String[] args)
{
int height[] = { 2, 1, 3, 4, 6, 5 };
int n = height.length;
System.out.print(maxWater(height, n));
}
}
Python3
# Python3 implementation of the above approach from functools import cmp_to_key def compareTo(p1,p2): return p1[1] - p2[1] # Return the maximum water that # can be stored def maxWater(height, n): # Make pairs with indices pairs = [0 for i in range(n)] for i in range(n): pairs[i] = [i, height[i]] # Sort array based on heights pairs.sort(key = cmp_to_key(compareTo)) # To store the min and max index so far # from the right minIndSoFar = pairs[n - 1][0] maxIndSoFar = pairs[n - 1][0] maxi = 0 for i in range(n-2,-1,-1): # Current building paired with # the building greater in height # and on the extreme left left = 0 if (minIndSoFar < pairs[i][0]): left = (pairs[i][1] * (pairs[i][0] - minIndSoFar - 1)) # Current building paired with # the building greater in height # and on the extreme right right = 0 if (maxIndSoFar > pairs[i][0]): right = (pairs[i][1] * (maxIndSoFar - pairs[i][0] - 1)) # Maximum so far maxi = max(left, max(right, maxi)) # Update the maximum and minimum so far minIndSoFar = min(minIndSoFar, pairs[i][0]) maxIndSoFar = max(maxIndSoFar, pairs[i][0]) return maxi # Driver code height = [ 2, 1, 3, 4, 6, 5 ] n = len(height) print(maxWater(height, n))
Javascript
<script>
// JavaScript implementation of the above approach
function compareTo(p1,p2)
{
return p1[1] - p2[1];
}
// Return the maximum water that
// can be stored
function maxWater(height, n)
{
// Make pairs with indices
let pairs = new Array(n);
for(let i = 0; i < n; i++)
pairs[i] = [i, height[i]];
// Sort array based on heights
pairs.sort(compareTo);
// To store the min and max index so far
// from the right
let minIndSoFar = pairs[n - 1][0];
let maxIndSoFar = pairs[n - 1][0];
let maxi = 0;
for(let i = n - 2; i >= 0; i--)
{
// Current building paired with
// the building greater in height
// and on the extreme left
let left = 0;
if (minIndSoFar < pairs[i][0])
{
left = (pairs[i][1] *
(pairs[i][0] -
minIndSoFar - 1));
}
// Current building paired with
// the building greater in height
// and on the extreme right
let right = 0;
if (maxIndSoFar > pairs[i][0])
{
right = (pairs[i][1] *
(maxIndSoFar -
pairs[i][0] - 1));
}
// Maximum so far
maxi = Math.max(left, Math.max(right, maxi));
// Update the maximum and minimum so far
minIndSoFar = Math.min(minIndSoFar,
pairs[i][0]);
maxIndSoFar = Math.max(maxIndSoFar,
pairs[i][0]);
}
return maxi;
}
// Driver code
let height = [ 2, 1, 3, 4, 6, 5 ];
let n = height.length;
document.write(maxWater(height, n),"</br>");
</script>
Producción:
8
Complejidad del tiempo: O(N*log(N))
Enfoque de dos punteros: tome dos punteros i y j que apunten al primer y último edificio respectivamente y calcule el agua que se puede almacenar entre estos dos edificios. Ahora incremente i si altura[i] < altura[j] sino disminuya j . Esto se debe a que el agua que puede quedar atrapada depende de la altura del edificio pequeño y moverse desde el edificio de mayor altura solo reducirá la cantidad de agua en lugar de maximizarla. Al final, imprime la cantidad máxima de agua calculada hasta el momento.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include<bits/stdc++.h>
using namespace std;
// Return the maximum water that can be stored
int maxWater(int height[], int n)
{
// To store the maximum water so far
int maximum = 0;
// Both the pointers are pointing at the first
// and the last buildings respectively
int i = 0, j = n - 1;
// While the water can be stored between
// the currently chosen buildings
while (i < j)
{
// Update maximum water so far and increment i
if (height[i] < height[j])
{
maximum = max(maximum, (j - i - 1) * height[i]);
i++;
}
// Update maximum water so far and decrement j
else if (height[j] < height[i])
{
maximum = max(maximum, (j - i - 1) * height[j]);
j--;
}
// Any of the pointers can be updated (or both)
else
{
maximum = max(maximum, (j - i - 1) * height[i]);
i++;
j--;
}
}
return maximum;
}
// Driver code
int main()
{
int height[] = { 2, 1, 3, 4, 6, 5 };
int n = sizeof(height)/sizeof(height[0]);
cout<<(maxWater(height, n));
}
// This code is contributed by CrazyPro
Java
// Java implementation of the approach
import java.util.Arrays;
class GFG {
// Return the maximum water that can be stored
static int maxWater(int height[], int n)
{
// To store the maximum water so far
int max = 0;
// Both the pointers are pointing at the first
// and the last buildings respectively
int i = 0, j = n - 1;
// While the water can be stored between
// the currently chosen buildings
while (i < j) {
// Update maximum water so far and increment i
if (height[i] < height[j]) {
max = Math.max(max, (j - i - 1) * height[i]);
i++;
}
// Update maximum water so far and decrement j
else if (height[j] < height[i]) {
max = Math.max(max, (j - i - 1) * height[j]);
j--;
}
// Any of the pointers can be updated (or both)
else {
max = Math.max(max, (j - i - 1) * height[i]);
i++;
j--;
}
}
return max;
}
// Driver code
public static void main(String[] args)
{
int height[] = { 2, 1, 3, 4, 6, 5 };
int n = height.length;
System.out.print(maxWater(height, n));
}
}
Python3
# Python3 implementation of the approach # Return the maximum water that can be stored def maxWater(height, n): # To store the maximum water so far maximum = 0 # Both the pointers are pointing at the first # and the last buildings respectively i = 0 j = n - 1 # While the water can be stored between # the currently chosen buildings while (i < j): # Update maximum water so far and increment i if (height[i] < height[j]): maximum = max(maximum, (j - i - 1) * height[i]) i += 1 # Update maximum water so far and decrement j elif (height[j] < height[i]): maximum = max(maximum, (j - i - 1) * height[j]) j -= 1 # Any of the pointers can be updated (or both) else: maximum = max(maximum, (j - i - 1) * height[i]) i += 1 j -= 1 return maximum # Driver code height = [2, 1, 3, 4, 6, 5] n = len(height) print (maxWater(height, n)) # This code is contributed by CrazyPro
C#
// C# implementation of the approach
using System;
class GFG
{
// Return the maximum water that can be stored
static int maxWater(int []height, int n)
{
// To store the maximum water so far
int max = 0;
// Both the pointers are pointing at the first
// and the last buildings respectively
int i = 0, j = n - 1;
// While the water can be stored between
// the currently chosen buildings
while (i < j)
{
// Update maximum water so far and increment i
if (height[i] < height[j])
{
max = Math.Max(max, (j - i - 1) * height[i]);
i++;
}
// Update maximum water so far and decrement j
else if (height[j] < height[i])
{
max = Math.Max(max, (j - i - 1) * height[j]);
j--;
}
// Any of the pointers can be updated (or both)
else
{
max = Math.Max(max, (j - i - 1) * height[i]);
i++;
j--;
}
}
return max;
}
// Driver code
static public void Main ()
{
int []height = { 2, 1, 3, 4, 6, 5 };
int n = height.Length;
Console.Write(maxWater(height, n));
}
}
// This code is contributed by jit_t
Javascript
<script>
// Javascript implementation of the approach
// Return the maximum water that can be stored
function maxWater(height, n)
{
// To store the maximum water so far
var maximum = 0;
// Both the pointers are pointing at the first
// and the last buildings respectively
var i = 0, j = n - 1;
// While the water can be stored between
// the currently chosen buildings
while (i < j)
{
// Update maximum water so far and increment i
if (height[i] < height[j])
{
maximum = Math.max(maximum, (j - i - 1) * height[i]);
i++;
}
// Update maximum water so far and decrement j
else if (height[j] < height[i])
{
maximum = Math.max(maximum, (j - i - 1) * height[j]);
j--;
}
// Any of the pointers can be updated (or both)
else
{
maximum = Math.max(maximum, (j - i - 1) * height[i]);
i++;
j--;
}
}
return maximum;
}
// Driver code
var height = [ 2, 1, 3, 4, 6, 5 ];
var n = height.length;
document.write(maxWater(height, n))
</script>
Producción:
8
Complejidad de tiempo: O(N)