[백준 6549] 히스토그램에서 가장 큰 직사각형 / 자바 / 스택

#문제         

레벨: P5
알고리즘: 스택
풀이시간: 1시간
힌트 참조 유무: 유

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

---

#문제 풀이        

이 문제는 스택문제이다. 여담으로 지금까지 푼 건물에 관한 문제는 스택이었다 크크. 스택에 넣고 빼는 규칙은 간단하다. 현재 건물이 Stack의 최상단보다 크면 Stack에 집어넣고 Stack의 최상단보다 작으면 현재건물보다 작은 것들을 다 빼서 넓이를 구한다. 그중 가장 큰 것이 정답이다.

 

빨간색 숫자는 높이를 의미한다. 높이가 2인 건물을 만나면 [1,4,5]가 담긴 숫자들을 빼며 넓이를 업데이트 한다. 일단 5x1= 5를 answer = Math.max(5,Long.MIN_Value)가 되고 2보다 4가 크니 4x2=8를 answer(8,5)가 된다. 

그 2를 넣는다. 그럼 stack에 [1,2]가 남는다. 건물을 다 순회했는데 이처럼 스택에 숫자가 남았다면 스택을 털어준다. 위와 같은 방식으로 넓이를 구하며.

---

#풀이 코드      

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());

            if (n == 0) break;

            long[] heights = new long[n];
            for (int i = 0; i < n; i++) {
                heights[i] = Long.parseLong(st.nextToken());
            }

            sb.append(getMaxArea(heights)).append("\n");
        }

        System.out.print(sb);
    }

    private static long getMaxArea(long[] heights) {
        Stack<Integer> stack = new Stack<>();
        long maxArea = 0;
        int i = 0;

        while (i < heights.length) {
            if (stack.isEmpty() || heights[stack.peek()] <= heights[i]) {
                stack.push(i++);
            } else {
                int top = stack.pop();
                long area = heights[top] * (stack.isEmpty() ? i : i - stack.peek() - 1);
                maxArea = Math.max(maxArea, area);
            }
        }

        while (!stack.isEmpty()) {
            int top = stack.pop();
            long area = heights[top] * (stack.isEmpty() ? i : i - stack.peek() - 1);
            maxArea = Math.max(maxArea, area);
        }

        return maxArea;
    }
}