给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
左边是是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
右边图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
示例:
输入: [2,1,5,6,2,3]
输出: 10
题意分析：
在图中找一块矩形，使其最大，并求最大的矩形面积
思路分析：
我们发现一个矩形能取多大的面积取决于边的高度，以及底边的长度
当边的高度选得越高，如题目图中选到了5，那么底部的长度自然会越小，因为并不是每一个小矩形的高度都达到了5
我们可以发现，当我们确定了矩形的高度之后，是有办法确定底边的长度的
即向两边扩展，直至找到第一个高度比自己低的矩形
例如示例中，我们选取2(index=4)作为高度，那么底边向左延伸可以到1(index1=1)，向右延伸可以到最右边(默认index2 = n,n为数组长度)
那么底边的长度即为index2-index1-1 = 6-1-1 = 4，能构成的面积为2*4=8。其余依此类推。
所以关键就在于对于一个index = i，如何去找到其左右两边第一个比nums[i]小的下标
这个步骤可以通过栈来完成，具体代码如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28# 60ms, beats 25.71%
class Solution(object):
def largestRectangleArea(self, nums):
# left[i] record the index of first num which smaller than nums[i] before i
# right[i] record the index of first num which smaller than nums[i] after i
n = len(nums)
stack = []
left = [-1] * n
for i in range(n):
while stack and nums[stack[-1]] >= nums[i]:
stack.pop()
if stack:
left[i] = stack[-1]
stack.append(i)
stack = []
right = [n] * n
for i in range(n-1,-1,-1):
while stack and nums[stack[-1]] >= nums[i]:
stack.pop()
if stack:
right[i] = stack[-1]
stack.append(i)
# 对每一个小矩形都判断一次，找最大面积
res = 0
for i in range(n):
res = max(nums[i]*(right[i]-left[i]-1), res)
return res