[Leetcode] Largest Rectangle in Histogram

Problem

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

For example, given [2,1,5,6,2,3], the largest rectangle is shown in the shaded area, which has area = 10 unit.

Algorithm 

Algorithm 

A histogram has O(n^2) rectangles. Each rectangle is determined by a left bar L, a right bar R and a "short bar", where the "short bar" has the minimum height in the range [L, R].  The height of the rectangle equals the height of the short bar, and the width is (R-L+1). 

For O(n^2) pairs of L and R, therefore, a brute force algorithm has a O(n^2) running time. 

Any bar in the histogram can be the short bar in one or more rectangles. Given a short bar, the height of the rectangle is fixed. Therefore, the rectangle with the maximum width has the maximum area. 

Question: how to find the L bar and R bar for a given short bar ? We need to maintain a data structure, such that, for a given short bar we can find its best L bar and R bar in O(1) time. 

Maintain a stack,  push bars ('s indices) into the stack in an non-descending order. If the current bar is shorter than the top of the stack, the top bar found its best L and R bars. Since the stack is in non-descending order, the top bar is higher than (top-1) element, also the current bar is shorter than the top element. Therefore, the top element found its L and R bar. 

Code