[BaekJoon] 6549 히스토그램에서 가장 큰 직사각형 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static StringBuilder answer = new StringBuilder();
    static Reader scanner = new Reader();

    static int rectangleCount;
    static int treeStartIndex;
    static int[] heights;
    static int[] segmentTree;

    static boolean input() {
        rectangleCount = scanner.nextInt();
        if (rectangleCount == 0) {
            return false;
        }
        heights = new int[rectangleCount];

        for (int idx = 0; idx < rectangleCount; idx++) {
            heights[idx] = scanner.nextInt();
        }

        return true;
    }

    /*
     * 세그먼트 트리 + 분할 정복을 통해 해결하는 문제
     * 특정 구간을 설정하였을 때 그 구간을 모두 포함하는 직사각형의 최대 넓이는 (구간 내의 가장 낮은 높이 * 구간 길이)이다
     * 그렇기 때문에 주어진 구간 내에서 가장 낮은 높이를 구하고 해당 높이 * 구간 길이를 통해 먼저 주어진 구간에서의 최대 직사각형 넓이를 구한다
     * 이후 가장 낮은 높이에 해당하는 곳을 기준으로 왼쪽과 오른쪽 각각 남은 구간들에 대해 같은 작업을 반복하여 각 구간에서의 최대 직사각형 넓이를 구한다
     *  - 만약 처음 구한 넓이가 아닌 다른 넓이가 최대 직사각형의 넓이라면 가장 낮은 높이를 가진 곳을 제외한 다른 구간에서의 직사각형의 넓이가 최댓값이 될 것이다
     *  - 그렇기 때문에 최소 높이를 구하고 해당 구간에서의 직사각형의 넓이를 구한 후, 최소 높이 위치를 제외한 다른 구간에서 마찬가지로
     *    최소 높이를 구한 후 직사각형의 넓이를 구하는 과정을 반복해나간다
     *
     * 이때 주어진 구간에서 최소 높이 위치를 구하는 것을 세그먼트 트리를 통해 구할 수 있다
     *  - 세그먼트 트리의 리프 노드에는 각 인덱스를 넣는다
     *  - 부모 노드에는 왼쪽 자식 노드와 오른쪽 자식 노드에 있는 인덱스에 해당하는 높이를 비교하고
     *    높이가 낮은 인덱스를 부모 노드에 넣는다.
     */
    static void solution() {
        int height = getHeight(rectangleCount);
        int nodeCount = getNodeCount(height);
        treeStartIndex = nodeCount / 2;
        makeSegmentTree(nodeCount, treeStartIndex);
        answer.append(getMaxArea(0, rectangleCount - 1)).append('\n');
    }

    static long getMaxArea(int startIndex, int endIndex) {
        int minHeight = findMinHeightIndex(startIndex, endIndex);

        long area = (endIndex - startIndex + 1) * (long) heights[minHeight];

        if (startIndex <= minHeight - 1) {
            long leftMaxArea = getMaxArea(startIndex, minHeight - 1);
            area = Math.max(area, leftMaxArea);
        }
        if (endIndex >= minHeight + 1) {
            long rightMaxArea = getMaxArea(minHeight + 1, endIndex);
            area = Math.max(area, rightMaxArea);
        }

        return area;
    }

    static int findMinHeightIndex(int start, int end) {
        int startIndex = treeStartIndex + start;
        int endIndex = treeStartIndex + end;
        int index = segmentTree[startIndex];

        while (startIndex <= endIndex) {
            if (startIndex % 2 == 1) {
                if (heights[index] > heights[segmentTree[startIndex]]) {
                    index = segmentTree[startIndex];
                }
            }
            if (endIndex % 2 == 0) {
                if (heights[index] > heights[segmentTree[endIndex]]) {
                    index = segmentTree[endIndex];
                }
            }

            startIndex = (startIndex + 1) / 2;
            endIndex = (endIndex - 1) / 2;
        }

        return index;
    }

    static int getHeight(int size) {
        return (int) Math.ceil(Math.log(size) / Math.log(2)) + 1;
    }

    static int getNodeCount(int height) {
        return Math.toIntExact(Math.round(Math.pow(2, height)));
    }

    static void makeSegmentTree(int nodeCount, int startIndex) {
        segmentTree = new int[nodeCount];
        Arrays.fill(segmentTree, -1);
        for (int idx = 0; idx < rectangleCount; idx++) {
            segmentTree[startIndex + idx] = idx;
        }

        for (int idx = startIndex - 1; idx > 0; idx--) {
            if (segmentTree[idx * 2] == -1) {
                segmentTree[idx] = -1;
                continue;
            }
            if (segmentTree[idx * 2 + 1] == -1) {
                segmentTree[idx] = segmentTree[idx * 2];
                continue;
            }
            if (heights[segmentTree[idx * 2]] <= heights[segmentTree[idx * 2 + 1]]) {
                segmentTree[idx] = segmentTree[idx * 2];
                continue;
            }
            segmentTree[idx] = segmentTree[idx * 2 + 1];
        }
    }

    public static void main(String[] args) {
        while (true) {
            if (!input()) {
                break;
            }
            solution();
        }
        System.out.print(answer);
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}