单调栈

• 保证栈中的元素递增或是递减
• 作用就是用来存放遍历过的元素
• 递增：栈底部的元素是最大的，也就是说，栈顶的元素是最小的
• 模版

int lens=temperatures.length;
int []res=new int[lens];
Deque<Integer> stack=new LinkedList<>();
stack.push(0);
for(int i=1;i<lens;i++){
    if(temperatures[i]<=temperatures[stack.peek()]){
        stack.push(i);
    }else{
        while(!stack.isEmpty()&&temperatures[i]>temperatures[stack.peek()]){
            res[stack.peek()]=i-stack.peek();
            stack.pop();
        }
        stack.push(i);
    }
}
return  res;

每日温度

• 单调栈里只需要存放元素的下标i就可以了，如果需要使用对应的元素，直接T[i]就可以获取。
• 递增的时候，栈里要加入一个元素i的时候，才知道栈顶元素在数组中右面第一个比栈顶元素大的元素是i。
• 如果求一个元素右边第一个更大元素，单调栈就是递增的，如果求一个元素右边第一个更小元素，单调栈就是递减的。
• 拿当前遍历到的元素和栈顶的元素比较
  • 当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况
    • 把当前元素下标加入栈顶
  • 当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况
    • 把当前元素下标加入栈顶
  • 当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况
    • 记录距离（下标相减）到result[st.top]，然后弹出栈顶元素下标，加入当前遍历元素下标到栈
• 遍历结束，如果还有下标在栈里，result[下标]=0，可以开始就初始化result[]所有的为0，这一步不用操作

下一个更大元素 I

• nums1 是 nums2 的子集，找出 nums1 中每个元素在 nums2 中的下一个比其大的值，返回数组，默认找不到为-1
• 遍历的当前元素和栈顶元素比较
  • 情况一：当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况 此时满足递增栈（栈头到栈底的顺序），所以直接入栈。
  • 情况二：当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况 如果相等的话，依然直接入栈，因为我们要求的是右边第一个比自己大的元素，而不是大于等于！
  • 情况三：当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况 此时如果入栈就不满足递增栈了，这也是找到右边第一个比自己大的元素的时候。

下一个更大元素 II

• nums1的下一个比其大的值，数组可以相连，环形
• 如何处理循环数组
  • 将两个nums数组拼接在一起，使用单调栈计算出每一个元素的下一个最大值，最后再把结果集即result数组resize到原数组大小就可以了
  • 可以不扩充nums，而是在遍历的过程中模拟走了两边nums，在使用i的时候进行取模i%nums.size，效率更高。比如nums.size=3，当i到4的时候，i已经越界了，但是取模后i又变成1了
  • 是否会覆盖原来下标的值？不会，我们只在 i < n 时才将索引压入栈，这样可以确保栈中的索引始终是原数组的索引。

接雨水

• 单调栈属于横向求解
• 要求左右两边都比当前元素大的第一个元素在哪
• 当前元素：栈顶元素，右边元素：当前遍历元素，左边元素：栈顶的下面一个元素
• 比如 30 栈顶10, 20]，三种情况
  • 情况一：当前遍历的元素（柱子）高度小于栈顶元素的高度 height[i] < height[st.top()] 此时满足递增栈（栈头到栈底的顺序），所以直接入栈。
  • 情况二：当前遍历的元素（柱子）高度等于栈顶元素的高度 height[i] == height[st.top()] 此时满足递增栈（栈头到栈底的顺序），所以直接入栈。也可以删除栈顶然后在入当前遍历元素，不影响结果
  • 情况三：当前遍历的元素（柱子）高度大于栈顶元素的高度 height[i] > height[st.top()] 此时如果入栈就不满足递增栈了，这也是找到右边第一个比自己大的元素的时候。
• 找到三个元素后开始计算
  • 记录当前栈顶元素，然后pop掉。现在左边就是栈顶了
  • 高度 = 左边和右边高度取最小值 然后减去中间柱子高度
  • 宽度 = 右边下标-左边下标-1
  • 如果当前遍历元素仍然大于栈顶，循环计算

柱状图中最大的矩形

• 如果当前柱子的左右两边都比当前柱子高，那么当前柱子可以向两边延伸，直到遇到比当前柱子矮的柱子
• 所以，这道题是求右边第一个比当前柱子矮的柱子，单调栈应该是递减的。
• 只有当前遍历的元素（柱子）高度小于栈顶元素的高度的时候，才需要计算面积。
• 在 height数组后，都加了一个元素0， 为什么这么做呢？
  • 如果数组本身就是升序的，例如[2,4,6,8]，那么入栈之后 都是单调递减，一直都没有走 计算结果的那一步，所以最后输出的就是0了
  • 那么结尾加一个0，就会让栈里的所有元素，都出栈计算一次。
• 在height数组前，也加了一个元素0， 为什么这么做呢？
  • 如果数组本身就是降序的，例如[8,6,4,2]，那么入栈之后 都是单调递减，一直都没有走 计算结果的那一步，所以最后输出的就是0了
  • 那么开头加一个0，就会让栈里的所有元素，都出栈计算一次。
• 单调栈的思路
  • 当前遍历的元素（柱子）高度小于栈顶元素的高度，就入栈
  • 当前遍历的元素（柱子）高度大于栈顶元素的高度，就计算面积
  • 当前遍历的元素（柱子）高度等于栈顶元素的高度，就更新栈顶元素