单调栈 LeetCode 42 84 85 503 739 901
单调栈在数据结构上与普通的栈没有任何不同，主要用到的操作依然为push, pop, peek。单调栈的特别之处主要在于栈的维护，需要保证栈内的元素按照特定的比较规则单调递增/递减。主要适用于需要对一段连续的数据进行比较来进行判断的情况。
在做单调栈之前，可以先看看这篇博客来对它的性质有个初步的理解。我自己在操练中认为单调栈并不需要看太多的文章，直接通过题目理解总结即可。标题已经列出了几道比较典型的单调栈的题目，这里我建议的刷题顺序为739->901->42->503->84->85
使用单调栈的时候，我认为要注意三点：
- 记录的是什么？下标 or 具体的值？
其实大部分题目最后要求的都会是记录下标，因为最后需要输出的不仅仅是值的相对大小，还有值与值之间的距离。当然如果只需要对值本身进行判断可以只存具体的值。
这里需要提一下901题。这一题由于原始数组并不是一次性给出的，因此需要对值和跨度同时进行记录， - 单调栈的单调性？
可以根据题目描述 or 相邻两元素的关系进行判断- 题目的描述
遗憾的是，大多数的题目都不会对单调性进行直接的描述，我个人认为可以思考如何将题目描述转化为“直到…为止”的句式，再以此进行判断。
比如第739题，我们可以将题目描述为：直到找到一个比温度X大的天数位置。因此很显然，本地所需要的单调栈是递减的。 - 直接对相邻元素进行判断
更加直接的方法是直接带入两个相邻的元素进行判断。当新增一个元素时，会对本身栈顶元素有何影响？
比如第42题，当新增的元素高于栈顶的元素时，能够形成蓄水池，同时会直接使比它低的栈顶元素作废（即弹出），因此42题所需要的单调栈应为递减的。
- 题目的描述
- 作为子问题 & 优化
其实单调栈有点类似贪心的思想，【永远确保当前值是最值】，如果不符合则弹出之前的值以确保最值。因此，在很多需要求最值的情况下，都可以考虑能否使用单调栈。典型的例子就是85题，它在每一行可以使用单调栈，最后综合每行最优得到全局最优。
同时还需要提到的是第739题的特殊解法，很巧妙的使用的倒序遍历。在倒序遍历之后其实这道题就变成了第901题科科，只不过由于这道题一次性完整的给出了原始数组，因此不必同时记录值和跨度，甚至直接用输出数组就OK，完全不需要额外开辟空间。
整体上，单调栈在时间、空间复杂度上都能达到O(n)的级别，而且思路往往比动态规划会简单和清晰。因此某些优化/最值题目如果想不出来动态规划的解法，不如考虑考虑单调栈。
