[0x11] 131.直方图中最大的矩形

题意

link（more：SPOJ1805）

如图，在水平线上有 \(n(n\leqslant10^5)\) 个宽度为 1 ，高度为 \(h(0\leqslant h\leqslant10^9)\) 的矩形，求包含于其中的最大子矩形面积。
例： \(h=\{2,1,4,5,1,3,3\};S_{max}=S_{阴影}\)

思路

首先简单模拟过程，可知当前高度受 \(h_i\) 的限制，以此向左右尽量扩边界 \(l_i,r_i\) ，得到当高度为 \(h_i\) 时的最大子矩形，在图中表现为：

不难看出，当 \(l_i,r_i\) 遇到第一个高度比 \(h_i\) 低的矩形时，就达到了最大边界。

∴易想到枚举所有矩形，每次向左右枚举得到 \(l_i,r_i\) 算出当前面积。

但该算法最坏复杂度显然达到 \(O(n^2)\) ，妥妥的超时。