[BOJ] 1725 히스토그램

문제

www.acmicpc.net/problem/1725

1725번: 히스토그램

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
	static int N, result;
	static int[] heights;
	static Stack<Integer> stack;
    public static void main(String[] args) throws IOException {
        //선언 및 입력
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        heights = new int[N+2];
        stack = new Stack<Integer>();
        
        for(int i=1;i<=N;i++)
        	heights[i] = Integer.parseInt(br.readLine());
        
        //계산
        stack.push(0);
        
        for(int i=1;i<=N+1;i++) {
        	while(!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
        		int tmp_idx = stack.pop();
        		result = Math.max(result, heights[tmp_idx]*(i-stack.peek()-1));
        	}
        	stack.push(i);
        }
        System.out.println(result);
    }
 
}