单调栈

单调栈

单调栈的定义与作用

单调栈的定义可以用一句话描述：单调递增或单调减的栈。单调栈是在执行的过程中不断的使栈变得单调，在这一过程中解决问题，单调栈通常适用于解决下一个更大或者下一个更小的问题。

用一个例子来更好地展示单调栈：

问题

给定一个整数数组 temperatures，表示每天的温度，返回一个数组 answer，其中 answer[i]是指对于第 i天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0来代替。

思路1（暴力破解）

这道题最简单直观地方法就是用两个for循环来查找，第一个for循环用i去扫描一遍temperatures ，第二个for循环去扫描i 到 temperatures.length-1 ，直到找到第一个大于temperatures[i] 的元素或者到达终点。这种方法的时间复杂度是O(n^2) 。

思路2（单调栈）

换个思路，这道题是典型的”找到下一个更大的元素”，如果我们在遍历时维护一个单调递增的栈结构，这个栈中包含所有的未找到下一个更高温度的元素，那么每次循环时只要去判断当前元素temperatures[i] 是否比栈顶元素大就可以找到下一个更大的元素，

具体做法是第一层循环时将所有元素扔到这个栈中，每次循环时都去判断一下当前元素(temperatures[i])是否大于栈顶元素，如果是，那么temperatures[i] 就是气温高于栈顶元素当前气温的那一天，栈顶元素出栈，然后下一个元素变为了栈顶元素，temperatures[i]继续栈顶元素比较，直到栈为空或者栈顶元素大于temperatures[i] ，然后将temperatures[i] 入栈。此时所有出栈的元素都找到了气温高于自身的天数，并且这个栈由于不断地比较与出栈，会一直保持单调递增的特性，如果到最后都没有遇到比其更大的元素，则说明temperatures 中没有比它们更大的元素，因此直接设置为0。

根据单调栈的特性，如果我们在第一层for 循环时能够维护一个单调递增的栈，栈顶元素就是从0到i-1中最大的元素，如果i能够大于栈顶元素，那么