[백준] 6549번 히스토그램에서 가장 큰 직사각형

문제 설명

https://www.acmicpc.net/problem/6549

문제 풀이

• 세그먼트 트리 + 분할 정복을 이용하여 풀이하였다.
• 우선 세그먼트 트리를 이용하여 특정 구간의 가장 높이가 낮은 지점의 인덱스를 저장한다.
• 이제 전체 구간의 최대 넓이를 구해야 하는데 모든 구간을 반복하면 시간초과가 발생한다.
• 가장 넓은 직사각형을 구할 때 방해가 되는 것은 구간 내 가장 낮은 높이의 블록이다.
  따라서, 특정 구간의 가장 낮은 높이의 인덱스를 기준으로 좌,우 구간의 최대 넓이를 계속 구해나가면 가장 큰 직사각형의 넓이를 구할 수 있다. (분할 정복)

소스 코드 (JAVA)

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

public class Main {
    public static BufferedReader br;
    public static BufferedWriter bw;

    public static int N;
    public static int[] arr;
    public static SegmentTree segTree;
    public static long result = Long.MIN_VALUE;

    public static class SegmentTree {
        int[] tree;

        public SegmentTree(int n) {
            double height = Math.ceil(Math.log(n) / Math.log(2)) + 1;
            long count = Math.round(Math.pow(2, height));
            tree = new int[Math.toIntExact(count)];
        }

        public int init(int node, int start, int end) {
            int mid = (start + end) / 2;
            if (start == end) return tree[node] = start;
            else {
                int leftMin = init(node*2, start, mid);
                int rightMin = init(node*2+1, mid+1, end);
                if (arr[leftMin] <= arr[rightMin]) return tree[node] = leftMin;
                else return tree[node] = rightMin;
            }
        }

        public int cal(int node, int start, int end, int left, int right) {
            int mid = (start + end) / 2;
            if (end < left || start > right) return N;
            else if (left <= start && right >= end) return tree[node];
            else {
                int leftChild = cal(node*2, start, mid, left, right);
                int rightChild = cal(node*2+1, mid+1, end, left, right);
                if (arr[leftChild] <= arr[rightChild]) return leftChild;
                else return rightChild;
            }
        }
    }

    public static void input() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
    }

    public static void recursive(int s, int e) {
        if (s == e) result = Math.max(result, arr[s]);
        else if (s < e) {
            int minIndex = segTree.cal(1, 0, N-1, s, e);
            result = Math.max(result, (long) (e - s + 1) * arr[minIndex]);
            recursive(s, minIndex - 1);
            recursive(minIndex+1, e);
        }
    }

    public static void solve() throws IOException {
        StringTokenizer st;
        while(true) {
            //초기화
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            if (N == 0) break;   //종료 조건
            arr = new int[N + 1];
            for (int i = 0; i < N; i++)
                arr[i] = Integer.parseInt(st.nextToken());
            arr[N] = Integer.MAX_VALUE;
            segTree = new SegmentTree(N);
            segTree.init(1, 0, N-1);
            result = Long.MIN_VALUE;

            recursive(0, N-1);
            bw.write(result + "\n");
        }
        bw.flush();
    }

    public static void main(String[] args) throws IOException {
        input();
        solve();
    }
}