-
8-8: 히스토그램에서 가장 큰 직사각형 찾기Stacks, Queues 2018. 10. 25. 21:31
히스토그램에서 가장 큰 직사각형 찾기
문제
히스토그램이란, 아래 그림과 같이 직사각형이 배열되어 있는 것을 말한다. 각 직사각형의 가로 길이는 1로 모두 같고, 세로 길이는 다를 수 있다. 예를 들어, 아래 그림은 높이가 2, 1, 4, 5, 1, 3, 3 인 직사각형으로 이루어진 히스토그램이다.
히스토그램이 주어질 때, 가장 큰 직사각형의 너비를 출력하는 프로그램을 작성하시오. 위의 예제에서는 최대 직사각형의 너비가 그림과 같이 8이다.
입력
첫째 줄에 히스토그램을 이루는 직사각형의 개수 N이 주어진다. ( 1 ≤ N ≤ 100,000 ) 둘째 줄에는 각 직사각형의 높이가 주어진다.
출력
최대 직사각형의 너비를 출력한다.
예제 입력
7 2 1 4 5 1 3 3
예제 출력
8
출처
University of Ulm local contest 2003 H
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;
public class histogram {
/**
*
*
*
*
*
*
* @param args
*/
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int histogram[] = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i=0; i<N; i++){
histogram[i] = Integer.parseInt(st.nextToken());
}
ArrayDeque<Integer> stack = new ArrayDeque<>();
int maxArea = 0;
for (int i=0; i<N; i++){
if (stack.isEmpty() || histogram[i] > histogram[stack.peek()]){
stack.push(i);
} else {
while (!stack.isEmpty() && histogram[i] <= histogram[stack.peek()]){
//use top of stack as height
int height = histogram[stack.peek()];
stack.pop();
int width = stack.isEmpty()? i: i - stack.peek()-1;
if (height*width > maxArea){
maxArea = height*width;
}
}
if (stack.isEmpty() || histogram[i] > histogram[stack.peek()]){
stack.push(i);
}
}
}
while (!stack.isEmpty()){
//use top of stack as height
int height = histogram[stack.peek()];
stack.pop();
int width = stack.isEmpty()? N: N - stack.peek()-1;
if (height*width > maxArea){
maxArea = height*width;
}
}
System.out.println(maxArea);
}
}'Stacks, Queues' 카테고리의 다른 글
8-9: 탑 (0) 2018.10.25 8-7: 괄호의 값 (0) 2018.10.25 8-5: 괄호 Valid Parentheses String (0) 2018.10.25 8-4: 원형 큐 구현하기 (0) 2018.10.25 8-3: 큐 구현하기 (0) 2018.10.25