单调栈

解决问题：解决最近邻较小或较大的问题；滑动窗口最大或最小值
用途： 可以以 O(1)的时间复杂度得知某个位置左右两侧比他大（或小）的数的位置，当你需要高效率获取某个位置左右两侧比他大（或小）的数的位置的的时候就可以用到单调栈。

• 求解数组中元素右边第一个比它小的元素的下标，从前往后，构造单调递增栈；
• 求解数组中元素右边第一个比它大的元素的下标，从前往后，构造单调递减栈；
• 求解数组中元素左边第一个比它小的元素的下标，从后往前，构造单调递减栈；
• 求解数组中元素左边第一个比它小的元素的下标，从后往前，构造单调递增栈。

单调栈里面存放的元素是数组下标的索引
（下面概念可能不一样，但是注意方向和单调性即可）
单调递减栈：栈底到栈顶依次递减从大到小排列，如下图所示。
单调递增栈：栈底到栈顶依次递增从小到大排列。

leetcode 739 每日温度

leetcode 每日温度

解题思路： 这道题既是求下一个比当前元素大的下标之差，即可以用上面的单调递减栈解决问题；当栈不为空并且当前元素比栈顶元素值大时，如上面图所示情形，先用临时变量记录栈顶的元素下标，然后将这个下标弹出，循环这个过程直到当前元素比栈顶元素小时退出循环，将这个下标入栈。

代码实现：

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        vector<int>res(T.size(),0);
        stack<int>sta;
        for(int i=0;i<T.size();i++){
            while(!sta.empty()&&T[i]>T[sta.top()]){
                int mp=sta.top();
                res[mp]=i-mp;
                sta.pop();
            }
            sta.push(i);
        }
        return res;
    }
};

leetcode 503 下一个更大的元素II

更大得元素II

解题思路：这题和上面温度类似，不同的是数组是循环的。

如何处理循环数组：

• 直接把两个数组拼接在一起，用单调栈解决下一个最大值；
• 采用滚动数组，模拟遍历两遍nums数组，用·i%nums.size()来操作；

代码实现

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int>res(nums.size(),-1);
        stack<int>sta;
        //这里用2倍的空间模拟
        for(int i=0;i<2*nums.size();i++){
            while(!sta.empty()&&nums[i%nums.size()]>nums[sta.top()%nums.size()]){
                int tmp=sta.top();
                res[tmp%nums.size()]=nums[i%nums.size()];
                sta.pop();
            }
            sta.push(i);
        }
        return res;
    }
};

leetcode 42接雨水

接雨水

解题思路：

解法1：暴力解法
针对每个高度，向左遍历得到左边的最大值，向右遍历得到右边的最大值，取两者的较小值减去当前的高度即为当前高度能接的雨水，遍历累加求和即可；

解法2：动态规划
优化暴力解法，获取最大值的过程每次都要遍历，可以开辟两个数组记录对应的最大值。
先从左向右遍历，记录每个下标对应从左边看最大值；
然后从右向左遍历，记录每个下标对应从右边看的最大值
最后遍历每个高度，取两者较小值减去当前的高度在累加

解法3：单调栈
采用单调递减栈，如果当前的条形块小于或等于栈顶的条形块，我们将条形块的索引入栈，意思是当前的条形块被栈中的前一个条形块界定。如果我们发现一个条形块长于栈顶，我们可以确定栈顶的条形块被当前条形块和栈的前一个条形块界定，因此我们可以弹出栈顶元素并且累加答案到 a n s ans ans，如下面图所示，当新加入的高度值大于栈顶元素时，说明可以形成凹字形，因为是单调递减栈，所以该元素的前面一个之一定比栈顶元素大，而新加如的元素也比栈顶元素大，所以可以计算雨水的值，内循环，发现这个值比栈顶元素依然大，说明还可以计算雨水值，直到比栈顶元素小，这个元素进栈，进入下一个循环，实际算法如下：

代码实现：

class Solution {
public:
    int trap(vector<int>& height) {
        if(height.size()==0) return 0;
        //解法1：暴力解法
        // int ans=0;
        // int size=height.size();
        // for(int i=1;i<size-1;i++){
        //     int max_left=0,max_right=0;
        //     //从右向左扫描,找到左边的最大值
        //     for(int j=i;j>=0;j--){
        //         max_left=max(max_left,height[j]);
        //     }
        //     //从左向右扫描，找到右边的最大值；
        //     for(int j=i;j<size;j++){
        //         max_right=max(max_right,height[j]);
        //     }
        //     ans+=min(max_right,max_left)-height[i];
        // }
        // return ans;
        /*解法2：动态编程
        int ans=0;
        int n=height.size();
        vector<int>left_max(n,0);
        vector<int>right_max(n,0);
        //从左向右扫描找到从左向右的最大值
        //两边边界一定要初始化;
        left_max[0]=height[0];
        for(int i=1;i<n;i++){
            left_max[i]=max(left_max[i-1],height[i]);
        }
        //从右向左扫描，找到从右向左的最大值
        right_max[n-1]=height[n-1];
        for(int i=n-2;i>=0;i--){
            right_max[i]=max(right_max[i+1],height[i]);
        }
        for(int i=1;i<n;i++){
            ans+=min(right_max[i],left_max[i])-height[i];
        }
        return ans;*/
        //解法3：单调栈
        int ans=0;
        stack<int>sta;
        for(int i=0;i<height.size();i++){
            while(!sta.empty()&&height[sta.top()]<height[i]){
                int tmp=sta.top();
                sta.pop();
                if(sta.empty()) break;
                int distance=i-sta.top()-1;
                int height_minlus=min(height[i],height[sta.top()])-height[tmp];
                ans+=height_minlus*distance;
            }
            sta.push(i);
        }
        return ans;
    }
};

leetcode 84 柱状图中的最大矩形

最大矩形面积


解题思路：

对于每一个高度，只要找到左边和右边第一个比这个值小的边界，即可得到这个高度的最大面积。
上图即为当高度为5时所能表示的最大面积，而要找到右边第一个较小的值既可以用单调栈来解决，从前向后遍历，采用递增栈，如果当前元素比栈顶元素小，即为右边第一个比栈顶元素小的值，而栈顶元素弹出之后，新的栈顶元素下标肯定为左边第一个较小值。因此可以计算出左右边界的距离，乘以该高度即为当前最大的面积。
计算过程是：每当有新元素入栈且小于栈顶元素时，先用临时变量记录此时的栈顶元素，弹出此元素之后的栈顶元素为左边的第一个较小值，计算距离乘以临时变量对应的高度即为之前栈顶元素对应的高度的面积，如果弹出之后，新元素仍然小于栈顶元素，弹出栈顶元素，在计算以这元素高度的面积，并且更新最大值。直到新元素大于栈顶元素时，入栈。

#include<vector>
#include<stack>
#include<iostream>
using namespace std;
int largestRectangleArea(vector<int>& heights) {
    int  res=0;
    stack<int>sta;
    heights.insert(heights.begin(),0);
    heights.push_back(0);
    for(int i=0;i<heights.size();i++){
        while(!sta.empty()&&heights[i]<heights[sta.top()]){
            int tmp=sta.top();
            sta.pop();
            int right=i;
            int left=sta.top();
            cout<<"原始的res为："<<res<<endl;
            cout<<"right= "<<right<<"left= "<<left<<"tmp= "<<tmp<<" "<<heights[tmp]<<"当前的面积为："<<(right-left-1)*heights[tmp]<<endl;
            res=max(res,(right-left-1)*heights[tmp]);
            cout<<"较大的为："<<res<<endl;
        }
        sta.push(i);
    }
    return res;
}
int main(){
    vector<int>heights;
    int n;
    for(int i=0;i<6;i++){
        cin>>n;
        heights.push_back(n);
    }
    int ret= largestRectangleArea(heights);
    cout<<"最终结果为："<<ret<<endl;
/*    for(int i=0;i<heights.size();i++){
        cout<<heights[i]<<" ";
    }*/
    return 0;
}

2 1 5 6 2 3
原始的res为：0
right= 2left= 0tmp= 1 2当前的面积为：2
较大的为：2
原始的res为：2
right= 5left= 3tmp= 4 6当前的面积为：6
较大的为：6
原始的res为：6
right= 5left= 2tmp= 3 5当前的面积为：10
较大的为：10
原始的res为：10
right= 7left= 5tmp= 6 3当前的面积为：3
较大的为：10
原始的res为：10
right= 7left= 2tmp= 5 2当前的面积为：8
较大的为：10
原始的res为：10
right= 7left= 0tmp= 2 1当前的面积为：6
较大的为：10
最终结果为：10