package com.duke.stack;

import java.util.Stack;

public class MaxRectangleAreaInHistrogram {

	public static void main(String[] args) {
		   int[] a = { 3, 2, 5, 6, 1, 4, 4 };
		// int a[] = { 6, 2, 5, 4, 5, 1, 6 };
		maxRectangleArea(a);
	}

	private static void maxRectangleArea(int[] a) {
		Stack<Integer> stack = new Stack<>();
		if (a == null || a.length == 0) {
			return;
		}

		int maxArea = 0;
		int i = 0;
		int area = 0;

		while (i < a.length) {
			if (stack.isEmpty() || a[stack.peek()] <= a[i]) {
				stack.push(i);
				i++;
			} else {
				int top = stack.pop();
				if (!stack.isEmpty()) {
					area = a[top] * (i - stack.peek() - 1);
				} else {
					area = a[top] * (i-top);
					System.out.println(area);
				}
				maxArea = Math.max(maxArea, area);
			}
		}
		
		while (!stack.isEmpty()) {
			int top = stack.pop();
			if (!stack.isEmpty()) {
				area = a[top] * (i - stack.peek() - 1);
			} else {
				area = a[top] * (i-top);
				System.out.println(area);
			}
			maxArea = Math.max(maxArea, area);
		}

		System.out.println("Max Histrogram Area:"+maxArea);
	}

}