单调栈

单调栈实际上就是栈，只是利用了一些巧妙的逻辑，使得每次新元素入栈后，栈内的元素都保持有序（单调递增或单调递减）。

Leetcode上有几道单调栈的问题。

• 496 「下一个更大元素 I」

  给你一个数组，返回一个等长的数组，对应索引存储着下一个更大元素，如果没有更大的元素，就存 -1。

默写单调栈模板解题
先判断是递增栈还是递减栈，这里判断为递减栈，套模板。

vector<int> nextGreaterElement(vector<int>& nums) {
    vector<int> res(nums.size()); // 存放答案的数组
    stack<int> s;
    // 倒着往栈里放
    for (int i = nums.size() - 1; i >= 0; i--) {
        while (!s.empty() && s.top() <= nums[i]) {
            // 不希望后面是矮个子
            s.pop();
        }
        // nums[i] 身后的 next great number
        res[i] = s.empty() ? -1 : s.top();
        // 
        s.push(nums[i]);
    }
    return res;
}

这就是单调队列解决问题的模板。for 循环要从后往前扫描元素，因为我们借助的是栈的结构，倒着入栈，其实是正着出栈。

• 739 每日温度

  给你一个数组T，这个数组存放的是近几天的天气气温，你返回一个等长的数组，计算：对于每一天，你还要至少等多少天才能等到一个更暖和的气温；如果等不到那一天，填 0。

稍微改下递减栈的模板。

vector<int> dailyTemperatures(vector<int>& T) {
    vector<int> res(T.size());
    // 这里放元素索引，而不是元素
    stack<int> s; 
    /* 单调栈模板 */
    for (int i = T.size() - 1; i >= 0; i--) {
        while (!s.empty() && T[s.top()] <= T[i]) {
            s.pop();//不希望后面的是更冷的天气
        }
        // 得到索引间距
        res[i] = s.empty() ? 0 : (s.top() - i); 
        // 将索引入栈，而不是元素
        s.push(i); 
    }
    return res;
}

• 503 下一个更大元素 II」

  
  现在假设 leetcode [496] 中的数组是环形的，还是返回下一个更大的元素。

比如输入一个数组[2,1,2,4,3]，你返回数组[4,2,4,-1,4]。拥有了环形属性，最后一个元素 3 绕了一圈后找到了比自己大的元素 4。
这个问题肯定还是要用单调栈的解题模板，但难点在于，比如输入是[2,1,2,4,3]，对于最后一个元素 3，如何找到元素 4 作为 Next Greater Number。
对于这种需求，常用套路就是将数组长度翻倍：

但是，我们不是真的将数组翻倍，而是利用循环数组的技巧来模拟数组长度翻倍的效果。

vector<int> nextGreaterElement(vector<int>& arr){
     vector<int> ret(arr.size());
    stack<int> stk;
    int N=arr.size();
    for(int i=2*N-1;i>=0;i--){
         while(stk.empty()==false&&arr[i%N]>=stk.top()){
             stk.pop();   
        }
        ret[i%N]=stk.empty()?-1:stk.top();
        stk.push(arr[i%N]);
    }
    return ret;
}

这样，就可以巧妙解决环形数组的问题，时间复杂度O(N)。