对应力扣题目-739. 每日温度

什么是单调栈？

单调递增栈,从栈底到栈顶依次递增（单调非递减栈:允许有相等）

单调递减栈,从栈底到栈顶依次递减（单调非递增栈:允许有相等）

单调栈的作用：

可以以 O(1) 的时间复杂度得知某个位置左右两侧比他大（或小）的数的位置，当你需要高效率获取某个位置左右两侧比他大（或小）的数的位置的的时候就可以用到单调栈。

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

范式：

单调递增栈

for(int i = 0; i < T.size(); i++){
    while(! stk.empty() && stk.top() > T[i]){
        ​stk.pop();
    }
    stk.push(A[i]);
}

单调递减栈

for(int i = T.size() - 1; i >= 0; i--){
    while(! stk.empty() && T[i] >= stk.top()){
        stk.pop();
    }         
    stk.push(i);
}