LC 84

Goal:
Given an array of non-negative integers which represent histograms with width of 1 and height of the integer value. Find the largest area of any consecutive histograms can form.

Intuition:
Max area must use one of the histogram as the height, thus we can calculate areas formed with every histogram as the height and find the max area.
The area of consecutive histograms can be expressed with following formula.
area = min(consecutive histograms) * distance between two ends.
The height of the area is determined by the shortest height among the consecutive histograms.

Explanation:
Maintain a non-decreasing stack and store indices of the values in the stack. while current value [i] is breaking the non-decreasing characteristic, we pop off the top of the stack [j], and we use [j] as the shortest bar to form an area. we can calculate the width by i-stack[-1]-1, and area = [j] * width and we pop the stack until non-decreasing stack is maintained again or the stack is empty. The reason we use non-decreasing stack is because for a element k in the stack, use k bar as the shortest bar to form an area and the area can only expand towards right side because all the bars on the right are taller, thus some portion of height k can be utilized for all the bars on the right. The left side of k is shorter so no need to include them.

Time: O(size of input)