[백준] 1725: 히스토그램 - JAVA

in Algorithm on 자료 구조

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

풀이

각 칸들의 높이가 주어지고, 내부에 가장 큰 직사각형을 구하는 문제이다.

아랫변을 구간으로 나눠 그 구간으로 이룰 수 있는 직사각형의 넓이를 비교해주었다.

세그먼트트리에는 구간별로 최소 높이를 갖는 인덱스를 저장해주었다.

구간으로 탐색할 때 인덱스를 기준으로 나누기 위함이다.

(1, N)구간에서 넓이를 구하면 밑변은 (N - 1 + 1)이 되고, 높이는 해당 구간의 최소 높이를 세그먼트트리에서 찾아주면 된다. 이렇게 구한것이 해당 구간에서 만들수있는 직사각형의 최대이다.

위에서 찾은 최소 높이의 인덱스를 idx라고 하면 (1, idx - 1), (idx + 1, N)으로 나누어 계속 진행한다.

메모리: 39272KB

시간: 356ms

언어: Java 11

코드

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

public class Main {

    static class SegmentTree {
        int[] tree;

        public SegmentTree(int arrSize) {
            tree = new int[arrSize * 4];
        }

        public int init(int node, int start, int end) {
            if (start == end) {
                return tree[node] = start;
            } else {
                int a = init(node * 2, start, (start + end) / 2);
                int b = init(node * 2 + 1, (start + end) / 2 + 1, end);
                return tree[node] = arr[a] < arr[b] ? a : b;
            }
        }

        public int find(int node, int start, int end, int left, int right) {
            if (left > end || right < start) {
                return 0;
            }

            if (left <= start && end <= right) {
                return tree[node];
            }

            int a = find(node * 2, start, (start + end) / 2, left, right);
            int b = find(node * 2 + 1, (start + end) / 2 + 1, end, left, right);
            return arr[a] < arr[b] ? a : b;
        }
    }

    static int N;
    static long[] arr;
    static SegmentTree seg;
    static long ans;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        arr = new long[N + 1];
        for (int i = 1; i < N + 1; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        arr[0] = Long.MAX_VALUE;

        seg = new SegmentTree(N);
        seg.init(1, 1, N);

        ans = 0;
        solve(1, N);

        System.out.println(ans);
    }

    private static void solve(int left, int right) {
        if (left > right) {
            return;
        }

        int idx = seg.find(1, 1, N, left, right);
        ans = Math.max(ans, arr[idx] * (right - left + 1));

        solve(left, idx - 1);
        solve(idx + 1, right);
    }

}