Envío 6891

Problema 0x4f - Rectángulo de máxima área dentro de un histograma pequeño

Autor: Aaron Zuñiga
Fecha: 2023-02-25 07:09:03 UTC (Hace alrededor de 1 año)

Caso #	Resultado	Tiempo	Memoria
#1	Correcto Note: Main.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details.	0.071 s	16 KBi
#2	Correcto Note: Main.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details.	0.064 s	16 KBi
#3	Correcto Note: Main.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details.	0.101 s	13 KBi
#4	Correcto Note: Main.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details.	0.102 s	13 KBi
#5	Correcto Note: Main.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details.	0.099 s	13 KBi
#6	Correcto Note: Main.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details.	0.126 s	13 KBi
#7	Correcto Note: Main.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details.	0.112 s	13 KBi
#8	Correcto Note: Main.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details.	0.129 s	13 KBi
#9	Correcto Note: Main.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details.	0.126 s	18 KBi
#10	Correcto Note: Main.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details.	0.096 s	13 KBi
#11	Correcto Note: Main.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details.	0.102 s	13 KBi
#12	Correcto Note: Main.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details.	0.093 s	13 KBi
#13	Correcto Note: Main.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details.	0.067 s	16 KBi
#14	Correcto Note: Main.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details.	0.108 s	13 KBi
#15	Correcto Note: Main.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details.	0.107 s	13 KBi
#16	Correcto Note: Main.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details.	0.125 s	13 KBi
#17	Correcto Note: Main.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details.	0.105 s	13 KBi
#18	Correcto Note: Main.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details.	0.108 s	13 KBi
#19	Correcto Note: Main.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details.	0.105 s	13 KBi

Puntos totales: 100 / 100

Código

import java.util.Scanner;
import java.util.Stack;
class Main
{
    public static void main(String[] args){
        
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a[] = new int[n+1];
        Stack stack = new Stack();
        int area = 0;
        int mayor = Integer.MIN_VALUE;
        
        for(int i = 0; i < n; i++){
            a[i] = sc.nextInt();
        }
        
        stack.push(0);
        for(int i = 1; i < a.length; i++){
            if(i == a.length - 1){
                a[i] = 0;
            }
            if(a[i] > a[i-1]){
                stack.push(i);
            }else{
                while(!stack.isEmpty()){
                    int x = (int)stack.peek();
                    if(a[x] <= a[i]){
                        stack.push(i);
                        break;
                    }
                    stack.pop();    
                    if(stack.isEmpty()){
                        area = a[x] * i;
                        if(area > mayor){
                            mayor = area;
                        }
                        stack.push(i);
                        break;
                    }else{
                        area = a[x] * (i - (int)stack.peek() - 1);       
                    }
                    if(area > mayor){
                        mayor = area;
                    }
                }
            }
        }
        System.out.println(mayor);
    }
}