上一篇:算法随笔_42: 寻找两个正序数组的中位数_方法2_二分查找-CSDN博客
=====
题目描述如下:
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1:
输入：heights = [2,1,5,6,2,3] 输出：10 解释：最大的矩形为图中红色区域，面积为 10
=====
算法思路:
根据题目的描述，我们发现相连的柱子数量要尽可能的多，这样能保证矩形的宽度尽可能的大。再有，相连柱子组成的矩形的高度取决于最低的那根柱子。那么我们是不是可以这样考虑:
最终矩形中的那根最低的柱子无非就是所有这些柱子中的其中一根。我们选择其中一根柱子如: p，把它认为是最终矩形中的最低的那根。然后计算出它能形成的最大矩形的面积p_area。
我们枚举数组中的所有柱子，都计算出相应的p_area，然后找出其中最大的那个p_area就是最终答案。
现在还剩一个问题: 如何高效的计算出p_area？
我们再回顾一下刚才的描述。柱子p是矩形中最低的那根，因此它所形成的最大矩形的高度就是p的高度。
那宽度怎么找呢？柱子p的左右两侧需要尽可能的向两边扩展，这样才能找到最大的宽度。根据题意，p左侧的那些柱子需要连续保持等于或高于p的高度，一旦低于p的高度，那么我们就找到了p所形成的最大矩形的左边界。同理，我们也可以像这样找到最大右边界。
前面的问题进一步细化，咱们如何高效的找出柱子p的最大左边界呢？
我们从左往右枚举一下数组heights来进一步分析一下:
1. 第一个元素heights[0]最大左边界就是它自己。
2. 如果heights[1]大于heights[0]，heights[1]最大左边界也是它自己。以此类推，如果数值连续递增，它们的最大左边界就是各自本身的位置。
3. 当出现第一次数值下降或相等的时候，比如heights[5] <= heights[4]，那heights[5]的最大左边界就是heights[4]，如果heights[5] 继续<= heights[3]，那heights[5]的最大左边界就是heights[3]，以此类推，直至碰到小于heights[5]的元素。
4. 如果后面数值又继续递增，那么就又回到了第2点的情形。如果递减或相等，就回到了第3点的情形。
根据这一系列的分析，我们发现，我们可以通过维护一个单调栈stck来完成所有柱子最大左边界的统计。我们设数组w_l存储每个柱子的最大左边界。w_r存储最大右边界。
我们从左往右枚举原数组，当数值不断递增时，我们把heights[i]加入stck。且w_l[i]就等于i。
当数值heights[i]下降或相等时，我们不断弹出栈顶元素stck[-1]，直到碰到小于heights[i]的元素，那么w_l[i]就等于当前的stck[-1]+1。加1，表示我们要取最后一个弹出的下标值才是最大左边界。如果stck为空，那么w_l[i]就等于0，即，数组的起始处。
枚举完所有元素后，就统计出了所有的最大左边界。
同理，我们从右往左，可以统计出每个柱子的最大右边界，并存入w_r。因为是从右往左枚举数组，所以当数值heights[i]下降或相等时，我们不断弹出栈顶元素stck[-1]，w_r[i]等于当前的stck[-1]-1。如果stck为空，那么w_r[i]等于n-1，数组的末尾。
完成所有的左右边界计算后，每个柱子就可分别计算出p_area。最大的p_area即为最终答案。
由于每个元素只会入栈一次，最多出栈一次，所以时间复杂度为O(n) 。下面是代码实现:
class Solution(object):def largestRectangleArea(self, heights):""":type heights: List[int]:rtype: int"""h_len=len(heights)w_r=[0]*h_lenw_l=[0]*h_lenstck=[]for i in range(h_len):while len(stck)>0 and heights[i]<=heights[stck[-1]]:stck.pop()w_l[i]=stck[-1]+1 if len(stck)>0 else 0stck.append(i)stck=[]for i in range(h_len-1,-1,-1):while len(stck)>0 and heights[i]<=heights[stck[-1]]:stck.pop()w_r[i]=stck[-1]-1 if len(stck)>0 else h_len-1stck.append(i)res=0for i in range(h_len):area=heights[i]*(w_r[i]-w_l[i]+1)res=max(res,area)return res
