前言

什么时候用单调栈呢？通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。
时间复杂度为$O(n)$。
单调栈的本质是空间换时间，因为在遍历的过程中需要用一个栈来记录右边第一个比当前元素大或小的元素，优点是只需要遍历一次。

739. 每日温度

典型的单调栈的模板！！！
那result[6] , result[7]怎么没更新啊，元素也一直在栈里。
其实定义result数组的时候，就应该直接初始化为0，如果result没有更新，说明这个元素右面没有更大的了，也就是为0。
情况一：当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况
情况二：当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况
情况三：当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况

class Solution{
    public:
    vector<int> dailyTemperatures(vector<int>& T){
        vector<int>result(T.size(), 0 );
        stack<int> st;<int>
        st.push(0);/WRONG T[0]
        for(int i = 1; i<T.size(); i++){
            if(T[i]<=T[st.top()]) st.push(i);///WRONG JUST st.top()
            else{
                while(! st.empty() && T[i]>T[st.top()]){
                    result[st.top()] = i-st.top();
                    st.pop();
                }
                st.push(i);
            }
        }
        return result;
    }
};

496. 下一个更大元素 I

用map来做映射
注意umap查找key只有count没有find！
C++中，当我们要使用集合来解决哈希问题的时候，优先使用unordered_set，因为它的查询和增删效率是最优的。

可以看出最后是要求nums1的每个元素在nums2中下一个比当前元素大的元素，那么就要定义一个和nums1一样大小的数组result来存放结果。
result数组如果某位置没有被赋值，那么就应该是是-1，所以就初始化为-1。
没有重复元素，我们就可以用map来做映射了。根据数值快速找到下标，还可以判断nums2[i]是否在nums1中出现过。

使用单调栈，首先要想单调栈是从大到小还是从小到大。本题和739. 每日温度是一样的。
栈头到栈底的顺序，要从小到大，也就是保持栈里的元素为递增顺序。只要保持递增，才能找到右边第一个比自己大的元素。

如下三种情况，一定要分析清楚。

情况一：当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况
此时满足递增栈（栈头到栈底的顺序），所以直接入栈。

情况二：当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况
如果相等的话，依然直接入栈，因为我们要求的是右边第一个比自己大的元素，而不是大于等于！

情况三：当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况
此时如果入栈就不满足递增栈了，这也是找到右边第一个比可能比 nums1 自己大的元素的时候。

判断栈顶元素是否在nums1里出现过，（注意栈里的元素是nums2的元素），如果出现过，开始记录结果。
（个人理解：维持n2 （i–顺序的）单调栈为主，找n1 （在n2 中的）第一个大为辅。。。）

记录结果这块逻辑有一点小绕，要清楚，此时栈顶元素在nums2中右面第一个大的元素是nums2[i]即当前遍历元素。

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {

        unordered_map <int,int>umap;///WRONG <int>(nums1.size());
        for(int i = 0; i<nums1.size(); i++){  umap[nums1[i]] = i;  }

        stack<int> st;WRONG  (nums2.size());
        st.push(0);///

        vector<int> result (nums1.size(),-1);
        if (nums1.size() == 0) return result;/

        for(int i = 1; i<nums2.size(); i++){
            if(nums2[i]<=nums2[st.top()]) st.push(i);
            else {
                while( !st.empty() && nums2[i]>nums2[st.top()]){//这是构建单调栈的基础与题目无关///WRONG while (umap.count(nums2[st.top()]) > 0) {

                    if (umap.count(nums2[st.top()]) > 0){这几行 if 才是题目相关
                        result[umap[nums2[st.top()]]] = nums2[i];
                    }

                    st.pop();//注意此处层次，在题目结束后一律pop
                }
                st.push(i);//注意此处层次，在while结束后
            }
            
        }
        return result;
    }
};

503. 下一个更大元素 II

不扩充nums，而是在遍历的过程中模拟走了两边nums。

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        stack<int> st;
        //st.push(0);
        vector<int> res(nums.size(),-1);
        if (nums.size() == 0) return res;//

        for(int i = 0; i<nums.size()*2; i++){
            //if(nums[i]<=nums[st.top()]) st.push(i);
            //else{
                while(!st.empty() && nums[i%nums.size()]>nums[st.top()]){
                        res[st.top()]=nums[i%nums.size()];
                        st.pop(); 
                    //}
                                       
                }
                st.push(i%nums.size());
        }

        return res;

    }
};
// class Solution {一些单调栈通用模板
// public:
//     vector<int> nextGreaterElements(vector<int>& nums) {
//         stack<int> st;
//         st.push(0);

//         vector<int> res(nums.size(),-1);

//         for(int i = 0; i<nums.size()*2; i++){
//             if(nums[i]<=nums[st.top()]) st.push(i);
//             else{
//                 while(!st.empty() && nums[i]>nums[st.top()]){
//                     if(xxx){
//                         xxx
//                     }
//                     st.pop();
//                 }
//                 st.push(i);
//             }
//         }

//         return res;

//     }
// };

42. 接雨水

第一个柱子和最后一个柱子不接雨水
注意只有h大于零的时候，在统计到总和中
双指针, 时间复杂度 n 平方，因此会超出时间限制

class Solution {
public:

    // int trap(vector<int>& height) {
    //     int res = 0;
    //     int left = 0;
    //     int right = 0;
    //     vector<int> water(height.size(), 0);

    //     for(int i = 1; i<height.size()-1; i++){
    //         left = height[i];
    //         right = height[i];
    //         for(int j = i-1; j>=0; j--){
    //             if(height[j]>height[i]) {
    //                 left = max(left, height[j]);
    //             }
    //         }
    //         for(int k = i+1; k<height.size();k++){
    //             if(height[k]>height[i]){
    //                 right = max(right, height[k]);
    //             }
    //         }
    //         water[i] = min(left,right)>height[i]? min(left,right) - height[i] : 0;
    //         res += water[i];
    //         //cout<<i<<" "<<water[i]<<endl;
    //     }
    //     return res;
    // }
//动归
    int trap(vector<int>& height){
        int res = 0;
        vector<int> dpl(height.size(), 0);
        vector<int> dpr(height.size(), 0);
        vector<int> water(height.size(), 0);
        if(height.size()<=2)return 0;

        for(int i = 0; i<height.size(); i++){
            dpl[i] = height[i];
            dpr[i] = height[i];
        }
        //必须以height【i】初始化，不能是0！！！
        for(int i = height.size()-2; i>=0; i--){
            dpr[i] = max(dpr[i+1], height[i]);
        }  
        for(int i = 1; i<=height.size()-2; i++){
            dpl[i] = max(dpl[i-1], height[i]);   
            water[i] = min(dpl[i], dpr[i]) - height[i];
            cout<<i<<" dpl "<<dpl[i]<<" dpr "<<dpr[i]<<endl;
            res+=water[i];
        }              
        return res;
    }

//单调栈：按行累计，略 
};

84.柱状图中最大的矩形(尚未）

动归：???
42. 接雨水
是找每个柱子左右两边第一个大于该柱子高度的柱子，而本题是找每个柱子左右两边第一个小于该柱子的柱子。