[Leetcode Solution] Largest Rectangle in Histogram

Analysis

• The O(n*n) algorithm is obvious
• for each rectangle with the high of i-th element, using two indices move to left and right separately to find the region in which every integer is bigger then i-th element. Then the size of rectangle equals to height of i-th element times the distance between two indices
• Based on this idea, O(n*n)is obvious. Iterate all the integer as the height integer, and find the formed rectangle size. 
• The O(n) algorithm is tricky however the behind idea is the same. The procedure that iterate all the integer and find out the rectangle formed by this integer is still needed. However for different integers, this find out procedure has a lot of common sub problems. So we can take advantage of this to do the O(n) algorithm.
• Use a stack to store the integers
• If the current integer is smaller then the element at the top of the stack, then push it into the stack
• If the current integer is bigger then the element at the top of the stack, calculation needs to be done
• The idea is the same
• Because the current integer is bigger then the top of stack, thus the rectangle formed by the top of stack cannot contain the current integer but contains the integer before current integer.
• Because the second to last integer in the stack is smaller then the integer at the top of stack, so the rectangle formed by the integer of top of stack  cannot contain the second to last integer. However it contains the integer after the second to last integers.
• At this time, the rectangle formed by the integer at the top of stack can be calculate
• Push back a integer 0 at the end of the vector to enforce all the rectangle is calculated.

Note

Code