Implementación de solución de cálculo de área máxima en Java

Clase 15 de 35 • Curso de Algoritmos Avanzados: Patrones de Arrays y Strings

Resumen

¿Cómo resolver el problema de contenedores con Java?

La implementación de soluciones de algoritmos en lenguajes de programación es una habilidad crucial para cualquier programador. Hoy abordaremos una solución para calcular el área máxima entre contenedores, utilizando Java. Si bien puedes emplear cualquier lenguaje para implementarlo, te mostraremos cómo estructurarlo adecuadamente en este lenguaje orientado a objetos.

¿Cuál es la estructura inicial en Java?

Antes que nada, es fundamental definir la clase y las variables que vamos a utilizar. Para este ejercicio, consideremos una clase llamada maxArea, cuyo objetivo es recibir como argumento un número de alturas y calcular el área máxima.

public class MaxArea {
    public int maxArea(int[] alturas) {
        int izquierda = 0;
        int derecha = alturas.length - 1;
        int areaMaxima = 0;
        
        while (izquierda < derecha) {
            int alturaMinima = Math.min(alturas[izquierda], alturas[derecha]);
            int base = derecha - izquierda;
            int areaActual = alturaMinima * base;
            areaMaxima = Math.max(areaMaxima, areaActual);
            
            if (alturas[izquierda] < alturas[derecha]) {
                izquierda++;
            } else {
                derecha--;
            }
        }
        return areaMaxima;
    }
}

¿Qué pasos seguir para calcular el área máxima?

Definición de variables: Necesitamos dos apuntadores, izquierda y derecha, los cuales inician al principio y al final del array de alturas respectivamente.
Cálculo del área actual: Lo hacemos multiplicando la diferencia de los índices derecha y izquierda por la mínima altura de las dos posiciones.
Actualización del área máxima: Se determina si el área calculada es mayor que el área máxima previamente almacenada.
Movimiento de los apuntadores: Como queremos maximizar el área, movemos el apuntador que apunta a la menor altura hacia el centro.

¿Cómo se prueba la implementación?

La prueba de nuestro algoritmo es esencial, no solo para garantizar su correcto funcionamiento, sino también para detectar errores lógicos. Al realizar pruebas de escritorio, verificamos paso a paso utilizando una entrada predefinida para confirmar que las operaciones se realizan correctamente. Veamos un ejemplo:

int[] alturas = {1, 8, 6, 2, 5, 4, 8, 3, 7};
MaxArea solucion = new MaxArea();
System.out.println(solucion.maxArea(alturas));

¿Es eficiente esta solución?

Complejidad temporal: La solución recorre el array de alturas una sola vez, lo cual representa una complejidad de (O(n)), siendo 'n' el número de alturas.
Complejidad espacial: Al almacenar solo un número constante de variables enteras, su complejidad espacial es (O(1)), es decir, constante.

Con estas optimizaciones, garantizamos que el algoritmo es tanto eficiente como efectivo al manejar conjuntos de datos grandes o variables en tiempo real.

Aprender a implementar y probar estas soluciones te ayudará considerablemente a mejorar tus habilidades como programador. Te animamos a seguir practicando y explorando otras posibles soluciones y complicaciones que puedan surgir en este tipo de problemas.

Nicolas Alpargatero

student•

He tomado muchos cursos de Platzi de programación y de verdad espero que la profe siga con el mismo ritmo de claridad y calidad, nadie se toma la delicadeza de explicar como ella. Hasta con cualquier lenguaje se hace entender. No como otros que solo transcriben y le toca a uno investigar cómo funciona.

Xavier Flores

student•

la mayoria de los cursos de back en JS son así jjjj

Juan Esteban

student•

Mi código en Go:

package main

import "fmt"

func calcArea(x int, y int, dis int) int {
	if x < y {
		return x * dis
	}
	return y * dis
}

func maxArea(nums []int) int {
	i, j := 0, len(nums)-1
	area, areaNow := 0, 0
	for i != j {
		areaNow = calcArea(nums[i], nums[j], j-i)
		if areaNow > area {
			area = areaNow
		}
		if nums[i] < nums[j] {
			i++
		} else {
			j--
		}
	}
	return area
}

func main() {
	heights := []int{1, 8, 6, 2, 5, 4, 8, 3, 7}
	fmt.Println(maxArea(heights))

	heights = []int{8, 1, 6, 2, 5, 4, 1, 3, 7}
	fmt.Println(maxArea(heights))
}

Reinaldo Mendoza

student•

Miguel Angel Reyes Moreno

student•

curioso que diga que usará Java y está programando en C#

Juan Pablo Carrasco Venegas

student•

Inicialmente pensé en hacer un ciclo anidado que recorrería la mitad de los elementos -- (esto, despues de pasar un día tratando de idear la manera de resolver ... :( ) -- pero despúes de ver la solución propuesta, y más optima, me quedó el código así:

function getMaxArea(alturas){
    let p1 = 0;
    let p2 = alturas.length-1;
    let maxArea = 0;
    while (p1<p2){
        let area = Math.min(alturas[p1],alturas[p2])*(p2-p1);
        maxArea = Math.max(area,maxArea)
        if (alturas[p1] > alturas[p2]) {
            p2--;
        }
        else{
            p1++;
        }
    }
    return maxArea;
}

Edgar Diego Piña Vargas

student•

¿Por que funciona este método de ir descartando las alturas más pequeñas partiendo de los extremos por sobre calcular y comparar todas las posibles áreas comparando izquierda por cada una de las derechas descartando por la izquierda para no repetir cálculos?

Valentín Jorge Begnis

student•

Entiendo la solución pero no entiendo por qué mueve los apuntadores de esa forma, creo que no se explica bien esa lógica

Francisco Javier Saavedra Alcala

student•

Es para obtener el area mayor sin necesidad de comparar todas las probabilidades lo cual seria posible pero con mayor complejidad algoritmica, la idea aqui es ir descartando las alturas menores e irte quedando con las mayores.

Germán Arenas Sánchez

student•

function maxArea(alturas) {

let area = 0;

let posi = 0;

let posf = alturas.length - 1

while (posi <= posf) {

if (alturas[posi] >= alturas[posf]) {

const areaTemp = alturas[posi] * (posf - posi -1)

if(areaTemp > area) area = areaTemp

posf -= 1

} else {

const areaTemp = alturas[posf] * (posf - posi -1)

if (areaTemp > area) area = areaTemp

posi += 1

}

return area;

}

John Eduard Meneses González

student•

Share my solution with JS

export function maxArea(alturas) {
  let izq = 0;  
  let der = alturas.length - 1;
  let maxAgua = 0;

  while (izq < der) {
    // Calcular área
    let alturaMin = Math.min(alturas[izq], alturas[der]);
    let ancho = der - izq;
    let area = alturaMin * ancho;

    // Actualizar el máximo si encontramos una mejor área
    maxAgua = Math.max(maxAgua, area);

    // Mover el puntero con menor altura para intentar maximizar el área
    if (alturas[izq] < alturas[der]) {
      izq++;
    } else {
      der--;
    }
  }

  return maxAgua;
}

Samuel Soto Hoyos

student•

Muy valiosa esta clase 10/10.

David Higuera

student•

export function maxArea(alturas) {
  // Tu código aquí 👈
  // pointer 1
  let p1 = 0;
  // pointer 2
  let p2 = alturas.length - 1;

  // greatest area found
  let area = 0;

  // find the greatest areas
  while (p1 < p2) {
    let h;
    const b = p2 - p1;

    if (alturas[p1] >= alturas[p2]) {
      h = alturas[p2];
      p2--;
    } else {
      h = alturas[p1];
      p1++;
    }

    if (b * h > area) area = b * h;
  }
  return area;
}

Angel Agustín Hernández Soledad

student•

Les comparto mi solución en Java:

public static int container(List<Integer> numbers ) {

        int apuntador1 = 0;
        int apuntador2 = numbers.size() - 1;

        int m = numbers.get(apuntador1);
        int n = numbers.get(apuntador2);

        int tmp1 = m;
        int tmp2 = n;

        for (int i = 1; i < (numbers.size() / 2); i++) {
            m = numbers.get(i - 1) - (i - 1) > m ? numbers.get(i - 1) : m;
            n = numbers.get(numbers.size() - i) - (i - 1) > n ? numbers.get((numbers.size() - i) -1 ) : n;

            if (m != tmp1) {
                apuntador1 = i - 1;
                tmp1 = m;
            }
            if (n != tmp2) {
                apuntador2 = (numbers.size() - i) -1 ;
                tmp2 = n;
            }
        }

        return Math.min(m,n) * (apuntador2 - apuntador1);
    }

Jose Agustin Narvaez Rivera

student•

Me gustaria saber una opinion extra a la mia, para terminarme de aclarar.

Cuando la profesora explica la primera iteracion dice que el areaActual es 7, pero en realidad seria 8; ya que la formula de la primera iteracion seria algo asi: areaActual = (8 - 0) * 1

porfavor si alguien me corrige ese punto de vista.

Bryan Castano

student•

Self.Observacion : Si bien es cierto que se debe ahorrar declarar variables extras para complejidad espacial S( 1 ) , esta Proffe se va al Extremo y manda toda la operacion en una sola Linea para no declarar mas Variables aux, lo que realmente no me gusta, ps el codigo se ve muy re cargado y mas dificil de entender para alguien que recien llegase a ver el >Codigo, \nYo pienso lo Ideal seria seria mantender un equilibrio entre O( n ) && S( 1 ) . sin recargar el codigo por lineas saturadas. \nEs mi Opinion Personal. \n Nunca Pares de Aprender\n \n .

Francisco Javier Saavedra Alcala

student•

Que elegancia hasta para debuguear, excelente maestra y excelente contenido 👍🏻

Ramon Angulo

student•

Mi solucion en JavaScript

function maxArea(heights) {
    let p1, p2, area;
  
    p1 = 0;
    p2 = heights.length - 1;
    area = 0;
  
    while (p1 !== p2) {
      let height1 = heights[p1], height2 = heights[p2];
      let minHeight = Math.min(height1, height2);
      let newArea = (p2 - p1) * minHeight;
  
      if (area < newArea)
        area = newArea;
      if (height1 < height2)
        p1++
      else
        p2--
    }
    return area;
  }

Harim Salazar Islas

student•

Comparto mi solución en C#

    int CalcularMayorArea(int[] miArreglo)
    {
        int areaMayor = 0;
        int p1 = 0;
        int p2 = miArreglo.Length - 1;

        while (p1 != p2)
        {
            int valor1 = miArreglo[p1];
            int valor2 = miArreglo[p2];
            int valorAMultiplicar = valor1 > valor2 ? valor2 : valor1;
            int resultado = valorAMultiplicar * (p2 - p1);

            if (resultado > areaMayor)
            {
                areaMayor = resultado;
            }

            if (valor1 >= valor2)
            {
                p2--;
            }
            else
            {
                p1++;
            }
        }

        return areaMayor;
    }

Tomas Santiago Cueva

student•

Desarollo una solución diferente en donde en vez de usar dos apuntadores, se utilizan solo dos maximos. Lenguaje de programación: Scala:

object ContainerWithMostWater {
  def algorithm(numList: List[Int]): Int = {
    var max1 = 0
    var max2 = 0

    for (number <- numList) {
      if (number > max1) {
        max2 = max1
        max1 = number
      } else if (number > max2) {
        max2 = number
      }
    }

    val container = max2 * max2
    container
  }

  def main(args: Array[String]): Unit = {
    val numberList = List(9, 8, 1, 2, 3, 11)
    println("The area of the largest rectangle is " + algorithm(numberList))
  }
}

ContainerWithMostWater.main(Array())

Diego Alejandro Albarracin Maldonado

student•

Mi versión del algoritmo actualizada hecha en C++

#include <bits/stdc++.h>
using namespace std;

int containerWithMostWater(int input[],int arraySize);
int calculateArea(int lengt, int width);
int updateVariable(int maxArea, int currentArea);

int main(){
    //Change the values of the array.
    int array1[]= {1, 8, 6, 2, 5, 4, 8, 3, 7};
    //Variable to storage the number of elements inside the array.
    int arraySize= sizeof(array1)/sizeof(array1[0]);
                                                //Calling the Function
    cout << "The Maximum possible area is: " << containerWithMostWater(array1, arraySize) << endl;
    return 0;
}

int containerWithMostWater(int input[], int arraySize){
    //Pointer 1
    int p1= 0;
    //Pointer 2
    int p2= arraySize-1;
    //MaxArea is a variable to save the maximum possible area
    //that a container can storage.
    int maxArea= 0;

    for (int i = 0; i < arraySize; i++)
    {
        //Comparisons to check which pointer has to be updated.
        if(input[p1]<input[p2]){
            maxArea = updateVariable(maxArea, calculateArea(input[p1], p2-p1));
            p1+=1;
        }else{
            maxArea= updateVariable(maxArea, calculateArea(input[p2], (p2-p1)));
            p2-=1;
        }
    }
    //Returns the maximum Area.
    return maxArea;
}

int calculateArea(int lengt, int width){
    //Returns the area of a rectangle, which is the shape that the container has.
    return lengt*width;
}

int updateVariable(int maxArea, int currentArea){
    //Returns the maximum value between the current calculated area and the maxArea
    //from the previous iteration.
    if(maxArea<currentArea){
        maxArea= currentArea;
    }
    return maxArea;
}

Armando Bueno

student•

Convertido a python:

def maxArea(heights):
    lp = 0 # left pointer
    rp = len(heights)-1 # right pointer
    maxArea = -1

    while lp < rp:
        # compute area
        area = (rp -lp + 1) * min(heights[lp], heights[rp])
        # get max. area
        maxArea = max(area, maxArea)
        # discard smallest value
        if heights[lp] < heights[rp]:
            lp += 1
        else:
            rp -= 1
    return maxArea

heights = [1,8,6,2,5,4,8,3,7]
print(maxArea(heights))

Victor Alfredo Matzar Say

student•

Comparto mi solución:

function maxArea(alturas) {
  let mayorArea = 0;
  let pointer1 = 0;
  let pointer2 = alturas.length - 1;
  while (pointer1 < pointer2) {
    let area = (pointer2 - pointer1) * Math.min(alturas[pointer1], alturas[pointer2]);
    if (area > mayorArea) mayorArea = area;
    alturas[pointer1] <= alturas[pointer2] ? pointer1++ : pointer2--;
  }
  return mayorArea
}

Implementación de solución de cálculo de área máxima en Java

Introducción

Patrones de Arreglos y Strings: Ventana Deslizante y Dos Apuntadores

Arrays y Strings: Funcionamiento y Complejidades Temporales

Dos Apuntadores

Patrón de Dos Apuntadores en Algoritmos de Lista

Verificación de Orden en Diccionario Alienígena

Ordenamiento de Palabras en Idiomas Alienígenas

Playground: Verifying Alien Dictionary

Ordenación de Palabras en Diccionario Alienígena

Combinar Listas Ordenadas en un Array Ascendente

Ordenamiento de Listas con Complejidad Óptima y Espacio Constante

Playground: Merge Two Sorted Lists

Intercalación de Listas Ordenadas en Python

Resolver el problema "Container with Most Water" en Python

Cálculo Óptimo de Área en Listas de Alturas

Playground: Container with Most Water