Longest Rectangle in histogram@leetcode

刷题必备书籍：Cracking the Coding Interview: 150 Programming Questions and Solutions 

简历：The Google Resume: How to Prepare for a Career and Land a Job at Apple, Microsoft, Google, or any Top Tech Company
算法学习书籍：Introduction to Algorithms
编程珠玑：Programming Pearls (2nd Edition)
C++ 学习：The C++ Programming Language, 4th Edition
经典操作系统书籍，龙书：Operating System Concepts
创业：The Start-up of You: Adapt to the Future, Invest in Yourself, and Transform Your Career

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.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given height = [2,1,5,6,2,3],
return 10.

» Solve this problem

这题我想了好久，也没想出来，看到网上各位大神也没想出来，我很安慰～有一个用一个栈来做，O(n)的时间，具体就是若是当前元素比栈顶元素大，就入栈，不然就看栈是不是空的，然后计算sum=max(sum, h[tmp]*(S.empty()? i : i-S.top()-1));
来计算sum，并且后面要i--，相当于对于已经出栈过后的栈顶元素与当前元素再比较一遍。

好吧，此题的精髓就在后面S.empty()? i : i-S.top()-1 这个上面，而且stack里面要存index，i-S.top()-1计算了长方形的宽，我们把它们叫做高度和宽度吧，这样计算了每一步往左找的最大长方形。