히스토그램 최대 넓이

전처리

static class Pair
{
    int index;
    int height;

    Pair(int index, int height) { this.index = index; this.height = height; }
}

 

 

히스토그램 최대 넓이

static int Histogram_Max_Space (int[] hist, int N)
{
    int ans = 0;
    Stack<Pair> stack = new Stack<>();

    for (int i=0; i<N; i++)
    {
        int height = hist[i];

        Pair current = new Pair(i, height);

        int changed_index = i;

        if ( stack.isEmpty() )
        {
            stack.push(current);
            continue;
        }

        while ( !stack.isEmpty() && stack.peek().height > current.height )
        {
            Pair poped = stack.pop();
            int space = poped.height * ( current.index - poped.index );
            ans = Math.max(ans, space);
            changed_index = poped.index;
        }

        current.index = changed_index;

        stack.push(current);
    }

    while ( !stack.isEmpty() )
    {
        Pair poped = stack.pop();
        int space = poped.height * ( N - poped.index );
        ans = Math.max(ans, space);
    }

    return ans;
}