[BOJ/백준] 1725 - 히스토그램

1725번: 히스토그램

---

세그먼트트리 : 최소 Height를 갖는 Index 저장

분할 정복 : 최소 Height를 기준으로 왼쪽 범위, 오른쪽 범위 다시 분할 정복

---

---

• 제목

히스토그램

---

• 조건

시간 제한 : 0.7 초

메모리 제한 : 128 MB 

---

• 문제

히스토그램에 대해서 알고 있는가? 히스토그램은 아래와 같은 막대그래프를 말한다.

각 칸의 간격은 일정하고, 높이는 어떤 정수로 주어진다. 위 그림의 경우 높이가 각각 2 1 4 5 1 3 3이다.

이러한 히스토그램의 내부에 가장 넓이가 큰 직사각형을 그리려고 한다. 아래 그림의 빗금 친 부분이 그 예이다. 이 직사각형의 밑변은 항상 히스토그램의 아랫변에 평행하게 그려져야 한다.

주어진 히스토그램에 대해, 가장 큰 직사각형의 넓이를 구하는 프로그램을 작성하시오.

---

• 입력

첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 자연수 또는 0이다.

---

• 출력

첫째 줄에 가장 큰 직사각형의 넓이를 출력한다. 이 값은 20억을 넘지 않는다.

---

예제 입력1	예제 출력1
7 2 1 4 5 1 3 3	8

---

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

public class Main{
    static StringBuilder sb = new StringBuilder();
    static int N, answer = Integer.MIN_VALUE;
    static int[] arr, segmentTree;
    static int init(int left, int right, int node){
        if(left == right) return segmentTree[node] = left;
        int mid = (left + right) / 2;
        int leftindex = init(left, mid, node * 2);
        int rightindex = init(mid + 1, right, node * 2 + 1);
        return segmentTree[node] = arr[leftindex] > arr[rightindex] ? rightindex : leftindex;
    }
    static int query(int left, int right, int node, int start, int end){
        if(end < left || right < start) return 0;
        if(start <= left && right <= end) return segmentTree[node];
        int mid = (left + right) / 2;
        int leftindex = query(left, mid, node * 2, start, end);
        int rightindex = query(mid + 1, right, node * 2 + 1, start, end);
        return arr[leftindex] > arr[rightindex] ? rightindex : leftindex;
    }

    static void findMax(int left, int right){
        int index = query(1, N, 1, left, right);
        answer = Math.max(answer, arr[index] * (right - left + 1));
        if(left == right) return;
        if(index - 1 >= left) findMax(left, index - 1);
        if(index + 1 <= right) findMax(index + 1, right);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        arr = new int[N + 1];
        arr[0] = Integer.MAX_VALUE;
        segmentTree = new int[1 << ((int)(Math.ceil(Math.log(N)/Math.log(2))) + 1)];
        for(int i = 1; i <= N; i++) arr[i] = Integer.parseInt(br.readLine());

        init(1, N, 1);

        findMax(1, N);

        System.out.println(answer);
    }
}