[BOJ] 1725. 히스토그램

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {		
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int heights[] = new int [N];
		for (int i = 0; i < heights.length; i++) {
			heights[i] = sc.nextInt();
		}
		int answer = 0;
		int min_height;
		
		// 밑면의 길이를 1로 고정한 후 값을 하나씩 증가시키며 반복.
		for (int width = 1; width <= N; width++) {
			// 최대 길이 내에서 시작 인덱스를 0으로 고정하고 한 칸씩 오른쪽으로 가면서 반복.
			for (int start_index = 0; start_index+width <= N; start_index++) { 
				// 밑면의 길이와 시작 인덱스를 고정할 때 마다 최소 높이를 구하기 위해서 초기화.
				min_height = Integer.MAX_VALUE; 
				// 최소 높이를 구하기위해 커서를 시작 인덱스부터 밑면의 길이만큼 한 칸씩 이동하며 구간을 탐색. 
				for (int cursor = start_index; cursor < start_index+width; cursor++) { 
					// 최소 높이를 구함.
					min_height = Math.min(min_height,heights[cursor]); 
				}
				// 이전까지의 후보들의 최대값과 비교해 더 큰 값을 정답 처리.
				answer = Math.max(answer,min_height*width); 
			}
		}
		System.out.println(answer); // 모든 최대 직사각형 후보들의 계산값 중 최대값을 정답으로 출력.
	}
}

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {		
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int heights[] = new int [N];
		for (int i = 0; i < N; i++) {
			heights[i] = sc.nextInt();
		}
		int answer = 0;
		int min_height;
		
		// 시작인덱스 0으로 고정한 후 한 칸씩 오른쪽으로 가면서 차례로 고정.
		for (int start_index = 0; start_index < heights.length; start_index++) {  
			// 종료인덱스를 시작인덱스의 한 칸 오른쪽 인덱스로 고정한 후 한 칸씩 오른쪽으로 가면서 차례로 고정.
			for (int end_index = start_index+1; end_index <= heights.length; end_index++) {
				// 시작 및 종료인덱스가 고정될 때마다 최소 높이를 구하기 위해서 초기화.
				min_height = Integer.MAX_VALUE; 
				// 시작인덱스부터 종료인덱스까지 커서를 한 칸씩 이동하며 최소 높이를 계산.
				for (int cursor = start_index; cursor < end_index; cursor++) {
					// 최소 높이를 구함.
					min_height = Math.min(min_height, heights[cursor]); 
				}
				// 이전까지의 후보들의 최대값과 비교해 더 큰 값을 정답 처리.
				answer = Math.max(answer,min_height*(end_index-start_index)); 
			}
		}
		System.out.println(answer); // 모든 최대 직사각형 후보들의 계산값 중 최대값을 정답으로 출력.
	}
}

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {		
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int heights[] = new int [N];
		for (int i = 0; i < heights.length; i++) {
			heights[i] = sc.nextInt();
		}
		int answer = 0;
		int min_height;
		int cursor = 0;
		// 시작 인덱스를 0으로 고정한 후 한 칸씩 오른쪽으로 가면서 차례로 고정.
		for (int start_index = 0; start_index < heights.length; start_index++) { 
			// 시작인덱스가 고정될 때마다 최소 높이를 구하기 위해서 초기화.
			// 종료인덱스가 고정될 때마다 초기화 하지 않는 이유는 이전 구간의 최소 높이로 재사용되기 때문
			min_height = Integer.MAX_VALUE;  
			for (int end_index = start_index+1; end_index <= heights.length; end_index++) {
				// 이전 구간에서 추가된 부분의 높이를 탐색할 커서위치.
				cursor = end_index-1; 
				// 우변의 Math.min 함수 내의 변수는 종료인덱스가 한 칸씩 오른쪽으로 이동할 때마다 이전 구간의 최소 높이로 사용.
				// 좌변의 변수는 이전 구간 최소높이와 커서위치 높이를 비교해서 현재 구간의 최소높이를 구함.
				min_height = Math.min(min_height, heights[cursor]); 
				// 이전까지의 후보들의 최대값과 비교해 더 큰 값을 정답 처리.
				answer = Math.max(answer,min_height*(end_index-start_index)); 
			}
		}
		System.out.println(answer); // 모든 최대 직사각형 후보들의 계산값 중 최대값을 정답으로 출력.
	}
}

import java.util.Scanner;
import java.util.Stack;

import java.lang.Math;

class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int heights []= new int [N+2];
		heights[0]=0;
		heights[N+1]=0;
		for (int i = 1; i <= N; i++) {
			heights[i] = sc.nextInt();
		}
		Stack<Integer> stack = new Stack<Integer>();

        long answer = 0;
		int width = 0;
		int i = 0;
		for (int cursor = 0; cursor < heights.length; cursor++) {
			while(!stack.isEmpty() && heights[stack.peek()] >= heights[cursor]){
				i = stack.peek();
				stack.pop();
				if(!stack.isEmpty())
					width = cursor - (stack.peek() + 1);
				
				answer = Math.max(answer, (long)(width)*heights[i]);
			}
			stack.push(cursor);		
		}
        System.out.println(answer);
	}
}