水平6549ヒストグラムで最大の長方形(Java、Java)

今回解決した問題.
これは白準6549号ヒストグラムの中で最大の矩形です.
📕 質問リンク
❗¥コード

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

public class Main {
    static int [] map;
    static int [] tree;
    static int N;
    static long answer;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        while(true)
        {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            if(N == 0) break;
            map = new int[N + 1];

            for(int i = 1; i <= N; ++i) map[i] = Integer.parseInt(st.nextToken());

            tree = new int[N * 4];
            setTree(1,N,1);

            answer = Long.MIN_VALUE;
            getMaxArea(1,N);

            sb.append(answer).append("\n");
        }
        System.out.print(sb);
    }
    static int setTree(int start, int end, int node)
    {
        if(start == end) return tree[node] = start; // 리프노드

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

        return tree[node] = map[left] < map[right] ? left : right;
    }

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

        int mid = (start + end) / 2;
        int leftMin = getMinIdx(start,mid,left,right,node * 2);
        int rightMin = getMinIdx(mid+1,end,left,right,(node * 2) + 1);

        if(leftMin < 0) return rightMin;
        else if(rightMin < 0) return leftMin;
        return map[leftMin] < map[rightMin] ? leftMin : rightMin;
    }

    static void getMaxArea(int start, int end)
    {
        if(start > end) return;
        int idx = getMinIdx(1,N,start,end,1);
        answer = Math.max(answer,(long)map[idx] * ((end - start) + 1));

        getMaxArea(start,idx-1);
        getMaxArea(idx+1,end);
    }
}

📝 に答える
N個の異なる高さのヒストグラムを入力すると、ヒストグラム範囲内で作成できる最大矩形幅を出力するのが問題です.
セグメントツリーを使用すると、ツリー内の各ノードに最低高さのインデックスがあります.
理由を理解するにはgetMaxArea関数を参照してください.
この関数は、まずgetMinIdx関数によって、現在の範囲内の最小高さのインデックスを取得します.取得するヒストグラムの範囲は、ツリーの初期化フェーズで作成した範囲と必ずしも一致しないため、getMinIdx関数を実装する必要があります.最も低い高さのインデックスが得られた場合、まずその高さを含む幅(横=startから末端範囲/縦=インデックスまでの高さ)を求める.答え値を最値に更新して下に進むと、受信した最小インデックスに基づいて左右分割征服が行われます.
ある範囲内で矩形の幅を求める場合、最大の制約条件は高さの違いであるため、その範囲内の最小インデックスに基づく高さの最値を求め、左/右範囲を征服するヒストグラムを分割して最値を更新することができる.
📜 ポスト
セグメントツリーは、基本的な問題のみを解いたため、非常に難しい問題かもしれません.
他のブログを見ると、画像と一緒にとても良い文章がたくさんあります!参考になると思います^^