[BOJ 6549번] 히스토그램에서 가장 큰 직사각형(JAVA)

https://www.acmicpc.net/problem/6549

6549번: 히스토그램에서 가장 큰 직사각형

import java.io.*;
import java.util.*;

class Main{
   
   static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
   static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
   
   public static void main(String args[]) throws Exception {
       while(true) {
          long max=0;
          String str[]=br.readLine().split(" ");
          int N=Integer.parseInt(str[0]);
          if(N==0) break; 
          Stack<Integer> stack=new Stack<>();
          long arr[]=new long[N];
          for(int i=0;i<N;i++) {
             arr[i]=Long.parseLong(str[i+1]);
          }
          for(int i=0;i<N;i++) {
             while(!stack.isEmpty()&&arr[stack.peek()]>arr[i]) {
                long h=arr[stack.pop()];
                int width=i;
                
                if(!stack.isEmpty()) {
                   width=i-stack.peek()-1;
                }
                
                max=Math.max(max, width*h);
             }
             stack.push(i);
          }
          while(!stack.isEmpty()) {
//        	  System.out.println("****");
             long h=arr[stack.pop()];
//             System.out.println("h:"+h);
             int width=N;
             if(!stack.isEmpty()) {
            	 width=N-stack.peek()-1;
//                 System.out.println("width:"+width);
             }
             max=Math.max(max, width*h);
          }
          
          System.out.println(max);
       }
   }
}

저는 이 문제를 스택을 이용해서 접근해보았습니다.

문제가 많이 어려워서 아래 링크를 참고해서 풀어보았습니다.

https://www.acmicpc.net/blog/view/12

히스토그램에서 가장 큰 직사각형

스택에 막대의 높이를 저장하는데, 이 때 규칙은 다음 막대가 현재 막대의 높이보다 작아야한다는 점입니다.

스택에 막대를 pop하면서 스택에서 꺼내온 막대들을 이용해서 만들 수 있는 직사각형 넓이의 최댓값을 구해줍니다.

이 값을 비교하면서 직사각형 넓이의 최댓값을 구하는데요, 위에 백준 님께서 작성하시는 글에 보다 자세한 과정이 나와 있으니 참고하시면 많은 도움이 될 것 같습니다.