- 84.柱状图中最大的矩形
需要找到元素i的上一个更小的元素leftmin和下一个更小的元素rightmin，这样leftmin和rightmin之间的元素都比当前元素i更大，那么矩形的宽就是中间的这些元素：可以从leftmin+1延伸到rightmin-1，长即为height[i]。
如下图，5的上一个更小是1，下一个更小是2，所以中间的5、6组成的矩形是以5为高的矩形中最大的，以此类推，以6为高最大是6、以2为高最大是2……
所以整体过程：从0出发，找到以height[栈顶]为高的时候面积最大的矩形，进行比较迭代得到maxarea。
找面积最大矩形就是上面的方法，上一个更小元素就得是次栈顶，下一个更小元素是遍历的元素，那么跟上题接雨水很相似。根据要求，必须使用单调递减栈。
当i比栈顶小，说明i是栈顶的下一个更小元素，那么得到栈顶是mid，上一个更小元素left=次栈顶，下一个更小元素是i，以height[mid]为高的矩形，面积最大的时候就是此时得到：宽为i-left-1。得到面积然后更新maxarea。
当i==栈顶，这里可以更新栈顶，也可以不更新。和接雨水一样，只用到了其元素值而没有用到其下标。
当i>栈顶，就应该直接入栈，不用计算面积，因为以栈顶为高的面积肯定不是最大面积。
如果只是把接雨水的题目改一下条件，将单增栈改为单减栈，程序还是会不对。
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int maxarea=0;
int n=heights.size();
stack<int> st;
st.push(0);
//找下一个比自己小的
for(int i=1;i<n;++i){
while(!st.empty() && heights[i]<heights[st.top()]){
int mid = st.top();
st.pop();
if(!st.empty() ){
int w=i-st.top()-1;
int h=heights[mid];//min(heights[i],heights[st.top()]);
maxarea=max(w*h,maxarea);
}
}
cout<<maxarea<<endl;
st.push(i);
}
return maxarea;
}
};比如：
5入栈，4更小，得到right(1)，mid（0），要得到left次栈顶，5出栈，栈则为空了，没有left，会跳过计算面积的过程，那么maxarea为0；4入栈，1更小，同样得不到left，maxarea还是0；1入栈，2更大，直接入栈，没有更新maxarea，所以结果是0。
当发生上面那种情况：数组里面存在这种连续递减的序列，而且这个序列的第一个元素进去的时候栈为空，就会持续上面的过程，所以方法是：在heights数组前面加一个0，这样栈里面永远都不会为空，不会跳过计算面积的过程，计算的时候left就为0，意味着栈顶左边没有比自己小的元素，这个矩形就从自己开始，到right-1。
那么如果是连续递增的序列：
1、2、3、4
1入栈，2更大，入栈；3更大，入栈……最后栈里面是这整个连续递增的序列，然后maxarea没有一次更新的过程，因为没有right，每个元素右边都没有比自己小的元素。解决方法是：在heights数组最后面加1个0，这样遍历最后这个元素0的时候，就会把栈里面这些元素都出栈然后计算面积。
所以单纯修改接雨水题目不行，还要解决这个最大矩形可能从自己开始（解决：heights开头加0）和以自己结尾（解决：heights开头加0）的情况。加入这两个之后，再在循环的时候从1开始，栈肯定不会为空，所以所有判断栈空的条件语句都可以省略了。
另外，加了这两个0对最后的结果也不会有影响。
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int maxarea=0;
heights.insert(heights.begin(),0);
heights.push_back(0);
int n=heights.size();
stack<int> st;
st.push(0);
//找下一个比自己小的
for(int i=1;i<n;++i){
while( heights[i]<heights[st.top()]){
int mid = st.top();
st.pop();
int w=i-st.top()-1;
int h=heights[mid];//min(heights[i],heights[st.top()]);
maxarea=max(w*h,maxarea);
}
cout<<maxarea<<endl;
st.push(i);
}
return maxarea;
}
};代码随想录训练营的内容，现在才刷完，一刷太慢看太细了，之后按照这个贴子的做法来：
第一遍：5~10分钟：读题+思考。如果不会直接看题解，然后理解题解中的解法，并且比较不同解法的时间和空间的复杂度(一定要对比，我面试的时候就被问了几种解法，一般都是时间最优或者空间最优的解法)。
第二遍：马上自己写一遍，然后提交(切记要根据自己看懂的思路来，而不是真的完全死记硬背)。多种解法比较。
第三遍：第二天重复做昨天的题，增加熟练度。
第四遍：一周后，再次写一遍，增加熟练度。
第五遍：面试前。
差不多就是这五步，当然时间不一定要这么精确，最重要是要多刷。至于为什么第一遍10分钟没思路就马上看题解呢？我认为我们写题并不是创造算法，所以如果不会还是老老实实的去看题解，不要死磕，否则效率会很低，如果有时间可以多想想也不错。
————————————————
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/qq_44713772/article/details/115870745
