问题描述直方图是由排列在同一基线上的相邻列组成的图形。输入是一个非负数数组，数组中的数字是直方图中条形的高度。假设直方图中bin的宽度为1，求出直方图中最大的矩形区域？例如：输入数组[3,2,5,4,6,1,4,3]，其对应的直方图如下图1所示，直方图中最大的矩形区域为12，如阴影部分所示:问题一个分析矩形的面积等于宽*高，所以只要先确定每个矩形的宽和高，就可以计算出矩形的面积。假设直方图中的一个矩形从索引为i的bin开始，到索引为j的bin结束。如何确定这个矩形的宽度和高度？宽度：(j-i+1)*1；height：i到j范围内高度最小的列的高度为矩形的高度。例如图1中下标2（i=2）的列与下标4（j=4）的列之间的矩形宽度为4-2+1=3；高度为4（三列之间的最小高度为4）。所以面积是4*3=12。暴力破解（枚举）如果可以枚举直方图中所有的矩形，比较它们的面积，就可以找到最大的矩形面积。这可以通过使用两个循环来实现。代码如下：2->4->3->1->6->7->5如图：时间复杂度假设输入数组的长度为n。直方图每列出栈一次，每列下标出栈时计算以它为顶的最大面积。这些操作的时间复杂度是每列的O(1)，所以这种单调栈方法的时间复杂度是O(n)。综上所述，这里得到一个大概的思路是：利用单调栈的特性，可以在线性时间内找到每个点左右第一个比它大/小的点。类似问题1.矩阵中的最大矩形问题。2.每日体温。3.下一个更大的数字问题。参考文献1.《剑指offer》2.3.《算法学习笔记(67): 单调栈》
