题目来源：
https://leetcode.com/problems/largest-rectangle-in-histogram/
题意分析：
给定一个数组，数组的数字代表这个位置上的bar的高度，在这些bar中找出最大面积的矩阵。例如height = [2,1,5,6,2,3]得到的图是
那么他的最大面积是
所以结果是10.
题目思路：
这是一道巧妙的算法题。首先，将bar的高度append到stack里，当遇到新的高度的时候就有3种情况，①如果newheight > stack[-1]，那么将这个高度append到stack里面；②如果相等，那么忽略；③如果newheight < stack[-1]，那么将stack里面的元素pop出来并且记录到这个高度的最大面积，直到stack为空，或者高度大于当前高度。
代码（python）：
1 class Solution(object): 2 def largestRectangleArea(self, heights): 3 """ 4 :type heights: List[int] 5 :rtype: int 6 """ 7 mans = 0 8 ans,ansindex,i = [],[],0 9 while i < len(heights): 10 if len(ans) == 0: 11 ans.append(heights[i]) 12 ansindex.append(i) 13 else: 14 if heights[i] >= ans[-1]: 15 ans.append(heights[i]) 16 ansindex.append(i) 17 else: 18 lastindex = 0 19 while len(ans) > 0 and ans[-1] > heights[i]: 20 tmp = ans.pop() 21 lastindex = ansindex.pop() 22 mans = max(mans,tmp*(i - lastindex)) 23 ans.append(heights[i]) 24 ansindex.append(lastindex) 25 i += 1 26 lastindex = 0 27 while len(ans) != 0: 28 tmp = ans.pop() 29 mans = max(mans,tmp*(len(heights) - ansindex.pop())) 30 return mans
[LeetCode]题解（python）：084-Largest Rectangle in Histogram
原文：http://www.cnblogs.com/chruny/p/5213588.html
