题目
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1:
输入：heights = [2,1,5,6,2,3] 输出：10 解释：最大的矩形为图中红色区域，面积为 10
示例 2：
输入： heights = [2,4] 输出： 4
解题
方法一：双指针
遍历每一个柱子，以该柱子的高度为矩形的高，计算左右指针的位置，确定矩形的宽。 （和接雨水那个题类似）
class Solution { public: int largestRectangleArea(vector<int>& heights) { int res=0; for(int i=0;i<heights.size();i++){ int left=i; int right=i; for(;left>=0;left--){ if(heights[left]<heights[i]) break; } for(;right<heights.size();right++){ if(heights[right]<heights[i]) break; } int w=right-left-1; res=max(res,w*heights[i]); } return res; } };
方法二：动态规划
class Solution { public: int largestRectangleArea(vector<int>& heights) { vector<int> minLeftIndex(heights.size()); vector<int> minRightIndex(heights.size()); int size = heights.size(); // 记录每个柱子 左边第一个小于该柱子的下标 minLeftIndex[0] = -1; // 注意这里初始化，防止下面while死循环 for (int i = 1; i < size; i++) { int t = i - 1; // 这里不是用if，而是不断向左寻找的过程 while (t >= 0 && heights[t] >= heights[i]) t = minLeftIndex[t]; minLeftIndex[i] = t; } // 记录每个柱子 右边第一个小于该柱子的下标 minRightIndex[size - 1] = size; // 注意这里初始化，防止下面while死循环 for (int i = size - 2; i >= 0; i--) { int t = i + 1; // 这里不是用if，而是不断向右寻找的过程 while (t < size && heights[t] >= heights[i]) t = minRightIndex[t]; minRightIndex[i] = t; } // 求和 int result = 0; for (int i = 0; i < size; i++) { int sum = heights[i] * (minRightIndex[i] - minLeftIndex[i] - 1); result = max(sum, result); } return result; } };
方法三：单调栈
要在height末端插入0, heights.push_back(0);
因为如果height是[2,4]，那么就不会执行while里面的内容了，导致结果是0，这一步就是起到哨兵的作用。
正常情况下（例子），当遇到2时，先计算红框的面积，6弹出，
要在height头部插入0，heights.insert(heights.begin(), 0);
因为如果height[2,1,2]，height变成[0,2,1,2,0] 最后堆栈只有（例子中是值，不是索引）[0,1]的时候，因为1前面的2，由于1的加入，1前面的2被堆栈弹出了。因此堆栈中，1前面的数一定是大于等于1的（因为全被1弹出了）。left为0的索引,cur为1的索引，可以得到结果3。
class Solution { public: int largestRectangleArea(vector<int>& heights) { heights.insert(heights.begin(),0); heights.push_back(0); stack<int> st; int res=0; for(int i=0;i<heights.size();i++){ while(!st.empty()&&heights[i]<heights[st.top()]){ int cur=st.top(); st.pop(); int left=st.top(); int right=i; res=max(res,(right-left-1)*heights[cur]); } st.push(i); } return res; } };
