[题目描述]givennnon-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 nit.给定n个非负整数表示直方图的条形高度,每个条的宽度为1,找到直方图中最大矩形的面积.以上是一个直方图,每个栏的宽度为1,高度= [ 2,1,5,6,2,3 ].最大矩形显示在阴影区域,面积为10单位.[题目链接] n,我们得到的包含该bar n的矩形区域里面bar n是最小的.我们使用ln和rn来表示bar n向左以及向右第一个小于bar n的bar的索引位置.譬如题目中的bar 2的高度为5,它的ln为1,rn为4.包含bar 2的矩形区域面积为(4 - 1 - 1) * 5 = 10.我们可以从左到右遍历所有bar,并将其p sh到一个stack中,如果当前bar的高度小于栈顶bar,我们pop出栈顶的bar,同时以该bar计算矩形面积.那么我们如何知道该bar的ln和rn呢?rn铁定就是当前遍历到的bar的索引,而ln则是当前的栈顶bar的索引,因为此时栈顶bar的高度一定小于pop出来的bar的高度.为了更好的处理最后一个bar的情况,我们在实际中会插入一个高度为0的bar,这样就能pop出最后一个bar并计算了.