一、什么是单调栈

单调栈（Monotone Stack）首先是个栈（Stack），那么它就会拥有栈所拥有的基本特性，即“先进后出，后进先出”的特点。

从名字上就听得出来，单调栈中存放的数据应该有序的，所以单调栈也可以分为单调递增栈和单调递减栈。

  • 单调递增栈：栈中数据出栈的序列为单调递增序列；
  • 单调递减栈：栈中数据出栈的序列为单调递减序列。

注意这里的递增与递减指的是出栈的顺序，而不是在栈中数据的顺序。

二、单调栈分析

分析单调栈问题的思路是：

  1. 暴力解法；
  2. 分析出“后进先出，先进后出”，所以可以用栈；
    说明：栈是一种缓存，恰恰好有些场景是后进先出。
  3. 分析出维护栈内单调性的原因；
  4. 记录结论：①上面四条；②栈内一般存下标；
  5. 多做题巩固。

单调栈的问题很有局限性，如果看到求左边第一个，右边第一个，大概就是单调栈。可以认为这一类问题其实就是认为设计出来的，让你维护栈内元素的单调性去做。此外，刷题是少不了的，多思考，多总结。这些知识不是看会的。

暴力解法与栈

  • 暴力解法的缺点通常都是时间复杂度高，但空间复杂度低，因为每一次计算后没有记住什么，暴力解法做了很多重复工作。
  • 所以一种解决方案就是使用“栈”作为缓存的数据结构，暴力解法的优化是：空间换时间。分析清楚“后进先出”能高效地解决这个问题
  • 具体分析的时候，拿具体例子（示例），画图分析思路，设计算法；
  • 最后再做优化。

栈到单调栈

  • 首先会考虑到栈（不是单调，题目给出的数据本来就没说单调，如果说单调的话，可能首选是二分法），后进先出；
  • 根据问题的特点，刚刚好栈里的元素呈单调减（增）的样子，这一类问题可以被认为是“被精心设计过的”，就是想不出来，没有关系，把它单做例题，去总结里面的思想；
  • 然后我们把这一类问题的解决方案，统称为“单调栈”，并且归纳出解决这一类问题的适用场景：
    保持这种单调性，就能找到：
    • 出栈元素左边第一个大于（等于）当前元素的位置；
    • 出栈元素左边第一个小于（等于）当前元素的位置；
    • 找右边第一个大于（等于）当前；如果看到解决问题需要有这种需求的，试试看用栈，往保持栈单调的方向思考，或许就能解决问题了。

不是因为这个问题很自然按照”单调栈“的样子而产生的，而是因为出题的人，为了让你用单调栈，故意把问题设计成这个样子。

  • 对于这类问题，建议是想清楚暴力解法，这一点特别关键。“滑动窗口”、“双指针”、“二分法”、“单调栈”、“动态规划”都是暴力解法的优化。从暴力解法的缺点去思考优化的解法。

三、题目举例

题目：视野总和

描述：有 n 个人站队，所有的人全部向右看，个子高的可以看到个子低的发型，给出每个人的身高，问所有人能看到其他人发型的总和是多少。

示例：

  1. 输入：4 3 7 1
  2. 输出：2
  3. 解释：个子为 4 的可以看到个子为 3 的发型，个子为 7 可以看到个子为 1 的身高，所以 1 + 1 = 2

image-20201009130324257.png

思路：观察完题目之后，我们发现实际上题意可以转化为找当前数字向右查找的第一个大于它的数字之间有多少个数字，然后将每个结果累计就是答案，但是这里的时间复杂度是 O(N^2)，所以我们可以利用单调栈做缓存来解决这个问题

  1. 设置一个单调递增的栈（栈内 0 ~ n 为单调递减）
  2. 当遇到大于栈顶的元素，开始更新之前不高于当前人所能看到的值

代码：

class Solution {

    /**
     * 每次入栈的时候，即栈顶元素大于入栈元素的时候，总和加上当前栈内元素个数
     */
    public int fieldSum(int[] height) {
        int ans = 0;
        Deque<Integer> stack = new LinkedList<>();

        for (int i = 0; i < hegiht.length; i++) {
            if (stack.isEmpty()) {
                stack.add(height[i]);
            } else {
                while (!stack.empty() && stack.peek() < height[i]) {
                    stack.pop();
                }
                ans += stack.size();
                stack.add(height[i]);
            }
        }

        return ans;
    }
}

四、数据结构

这里简单对几种常见的解题数据结构做个小结：

  • 单调栈首先是“栈”，解决这个问题的时候，处理的数据在顺序上有“后进先出”的特点；
  • 数据结构可以认为是一种缓存，是【空间换时间】思想的体现，恰当的数据结构可以帮助我们高效地处理数据，所谓恰当，是指“针对问题场景”，使用了合适的数据结构：
    • 栈：符合“后进先出”；
    • 队列：符合“先进先出”；
    • 哈希表：有快速存取数据的特点；
    • 二分搜索树（红黑树、B树系列）维护了数据的先后关系，还能得到一个数据的上下界；
    • Trie（字典树）：专门用于处理字符串的问题；
    • 并查集：用于处理不相交集合的动态连接问题；
    • 线段树：用于处理区间和；
    • 树状数组：用于处理前缀和；
    • 优先队列：用于处理有动态添加数组且需要获得最值的场景；
    • 单调队列、单调栈。
  • 学习建议
    • 先理解【暴力解法】（Brute Force），暴力解法通常是不占用空间的，挨个去算，每一个数据的计算都没有为下一个数据的计算留下些什么；
    • 学习这些数据结构，或者说使用这些数据结构的时候，要清楚，对数据的增删改查的意义是什么？
    • 画图（拿起纸笔，把思路讲清楚）：题目11、42、84，都是画图（物理现象）才能搞清楚思路和设计算法流程的问题；‘
    • 拿一般化的例子（研究算法思路）和特殊例子研究（算法细节 base case、corner case）面对 corner case 可能得用哨兵优化（单链表问题）；
    • 认真调试代码。