柱状图中最大的矩形
问题描述
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
暴力法
思路分析
以柱子i的高度为基准的最大矩形面积
时间复杂度O(nn) 超时
代码实现
动态规划
思路分析
dp[i][j] 代表以第i个柱子为尾，高度为j时的可以组成的最大矩形面积
* 时间复杂度O(nm)
* m很大时，空间溢出，可以对高度空间压缩
* n和m都很大时，O(nm) 超时
代码实现
栈
思路分析
单调非减栈
heights[s.top()]>heights[i]时,以s.top()为基准的最大矩形面积 height = heights[s.top()];
s.pop();
ans = max(ans, height * (i - s.top() - 1));
时间复杂度O(n)