[백준 1725] 히스토그램(Java)

문제 링크 : https://www.acmicpc.net/problem/1725

이 문제는 세그먼트 트리를 이용하여 풀 수 있습니다. 최대 면적의 히스토그램 면적은 범위 내의 가장 작은 높이 x 범위 구간의 길이가 됩니다. 이 때 세그먼트 트리의 특성상 특정 구간 내의 최소값을 빠르게 구할 수 있기 때문에 풀이에 적합합니다.

우선 트리에 인덱스 정보를 추가하는 방식으로 세그먼트 트리를 초기화합니다. 이 후 구간 내의 최솟값 인덱스를 구한 후 구간의 길이와 그 인덱스가 가리키는 원소의 값의 곱을 계산합니다.

여기서 현재 구간보다 왼쪽 혹은 오른쪽으로 더 확장 가능한지를 체크하기 위해 현재 인덱스 값을 좌우로 1씩 증가시키는 구간의 면적을 계산하여 최댓값을 갱신합니다.

다음은 코드입니다.

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

class Main{
    static int N;
    static int[] tree;
    static int[] arr;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        for(int i=0;i<N;i++) arr[i] = Integer.parseInt(br.readLine());

        int size = getTreeSize(N);
        tree = new int[size];
        init(1,0,N-1);
        System.out.println(getArea(0,N-1));
    }

    private static long getArea(int left, int right){
        int min = getMin(1,0,N-1,left,right);
        long area = (long)(right-left+1) * (long)arr[min];

        if(min+1 <= right){
            long newArea = getArea(min+1,right);
            area = Math.max(area, newArea);
        }
        if(min-1 >= left){
            long newArea = getArea(left,min-1);
            area = Math.max(area,newArea);
        }
        return area;
    }

    private static int getMin(int node, int start, int end, int left, int right){
        if(end<left || right<start) return -1;
        if(end<=right && left<=start) return tree[node];

        int mid = (start+end)/2;
        int leftIdx = getMin(node*2,start,mid,left,right);
        int rightIdx = getMin(node*2+1,mid+1,end,left,right);

        if(leftIdx == -1) return rightIdx;
        else if(rightIdx == -1) return leftIdx;
        else return arr[leftIdx] <= arr[rightIdx] ? leftIdx : rightIdx;
    }

    private static int getTreeSize(int N){
        int H = 0;
        int L = N;
        while(L>0){
            H++;
            L /= 2;
        }
        return (int) Math.pow(2,H+1);
    }

    private static void init(int node, int start, int end){
        if(start == end) tree[node] = start;
        else{
            int mid = (start+end)/2;
            init(node*2,start,mid);
            init(node*2+1,mid+1,end);

            if(arr[tree[node*2]] <= arr[tree[node*2+1]]) tree[node] = tree[node*2];
            else tree[node] = tree[node*2 +1];
        }
    }
}