// Problem 4: Max Area in Histogram
// -> Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

// Sample Input:
//  -> heights = [2, 1, 5, 6, 2, 3]
// Output:
//  -> 10

import java.util.*;
public class Main {
    public static int maxArea(int[] arr) {
        int maxArea = 0;
        int[] nextRight = new int[arr.length];
        int[] nextLeft = new int[arr.length];

        // next smaller right width
        Stack<Integer> s = new Stack<>();
        for(int i=arr.length-1; i>=0; i--) {
            while(!s.isEmpty() && arr[s.peek()] >= arr[i]) {
                s.pop();
            }
            if(s.isEmpty()) {
                nextRight[i] = arr.length;
            } else {
                nextRight[i] = s.peek();
            }

            s.push(i);
        }

        // next smaller left width
        s = new Stack<>();
        for(int i=0; i<arr.length; i++) {
            while(!s.isEmpty() && arr[s.peek()] >= arr[i]) {
                s.pop();
            }
            if(s.isEmpty()) {
                nextLeft[i] = -1;
            } else {
                nextLeft[i] = s.peek();
            }

            s.push(i);
        }

        // area
        for(int i=0; i<arr.length; i++) {
            int height = arr[i];
            int width = nextRight[i] - nextLeft[i] - 1;
            int area = height * width;

            maxArea = Math.max(area, maxArea);
        }
        return maxArea;
    }
    public static void main(String[] args) {
        int[] arr = {2, 1, 5, 6, 2, 3};
        System.out.println(maxArea(arr));
    }
}