单调栈

Handy
数据结构与算法
2022年4月26日

陈述

顾名思义，就是单调的栈，可严格可不严格。能够找到下一个更大/小的元素，同时能找到上一个大于等于/小于等于的元素。

通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了1。

一般可通过单调栈进行逆向思维，单调栈保存了目前没法求解的，过去已知的某些结论，如739. 每日温度、下一个更大元素 I，当然反向遍历正向思维也可以。
找下一个更大的元素？用单调不增栈记录过去的元素！回顾过去是容易的，要找将来是困难的。如果当前元素大于栈顶元素，那么栈里面所有小于当前元素的元素都可解。如果当前元素小于等于栈顶元素，那么进栈等待以后求解。
正向遍历可以，那反向遍历呢？也可以！反向遍历仍然是这个思路，记录过去的信息，是一个单调不增栈。如果当前元素小于栈顶元素，那么当前元素可求解，并可入栈。如果当前元素大于等于栈顶元素，那么进栈前顺便把过去的矮个子统统删除免得浪费空间。
找到下一个更大的元素，同时也能找到上一个更大的元素？单调不增栈，即非严格递减栈，遇到更小的直接入，遇到更大的，则栈里面的元素的下一个更大元素可解，同时每个元素由于非严格单调递减，故而上一个大于或等于的元素就是弹出当前元素后的栈顶。如84. 柱状图中最大的矩形。

每日温度

每次要求后面第一个比今天温度高的日子。

逆向思维，找过去比今天温度低的日子是不是更容易一点？

维护了一个单调不增的栈，这里面都是到目前为止没法立即算出来的日子。一旦遇到比栈顶温度高的日子，那么栈里面就能立即找到比当前温度低的所有日子，于是就不断地出栈求解。

正向遍历用的是逆向思维。反向遍历用的是正向思维。两者都是用的单调不增栈，具体的模拟可看图2。

class Solution {
  public int[] dailyTemperatures(int[] temperatures) {
    // 用栈来保存当前没法算出来的数组的索引
    LinkedList<Integer> stack = new LinkedList<>();
    int[] result = new int[temperatures.length];
    for (int i = 0; i < temperatures.length; i++) {
      while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {
        int prev = stack.pop();
        result[prev] = i - prev;
      }
      stack.push(i);
    }
    return result;
  }
}

反向遍历，每次当前元素都能求解，因为过去的比当前元素大的第一个元素能从栈顶得出。

class Solution {
  public int[] dailyTemperatures(int[] nums) {
    // 用栈来保存过去的信息，这是一个单调不减栈，能找到第一个比当前元素大的
    Deque<Integer> stack = new ArrayDeque<>();
    int[] ans = new int[nums.length];
    for (int i = nums.length - 1; i >= 0; i--) {
      while (!stack.isEmpty() && nums[i] >= nums[stack.peek()]) {
        stack.pop();  // 已经有更大的了，过去的小个子统统滚出去，别浪费空间
      }
      ans[i] = stack.isEmpty() ? 0 : stack.peek() - i;   // 直接得比当前元素更大的第一个元素
      stack.push(i);
    }
    return ans;
  }
}

时间复杂度 O(n)，最多进栈出栈一次。

下一个更大元素 I

跟每日温度一模一样的，正向遍历逆向思维，当然反向遍历也可。

用哈希表存储nums2中每个数字的下一个更大元素。

而nums2中每个数字的下一个更大元素如何求？类比每日温度，用逆向思维。在当前元素之后找比当前元素更大的元素是麻烦的，但是在当前元素之前找比当前元素更小的元素是容易的，因为可构建一个单调不增栈，专门来做这个事，记忆过去看到的元素！

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        // 用哈希表存储nums2中每个数字的下一个更大元素
        // 下一个更大元素，逆向思维前一个更小元素，同每日温度
        HashMap<Integer, Integer> map = new HashMap<>();
        Deque<Integer> monoStack = new ArrayDeque<>();  // 单调不增栈，放元素值
        for (int i = 0; i < nums2.length; i++) {
            while (!monoStack.isEmpty() && monoStack.peek() < nums2[i]) {
                int curr = monoStack.pop();
                map.put(curr, nums2[i]);
            }
            monoStack.push(nums2[i]);
        }
        // 结束后栈里面还有元素的话，就表示没有下一个更大的
        int[] ans = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            ans[i] = map.getOrDefault(nums1[i], -1);  // 找不到的是 -1
        }
        return ans;
    }
}

下一个更大元素II

这道题在上一道题的基础上，把数组变成了循环数组。

如何处理循环数组？

一般是以直代曲进行拼接，复制一个数组粘贴到原数组的后面呗，最后只留下前半部分即可。

但是这种方式增加了不必要的复杂度，其实可以在原数组上进行模拟拼接，先要搞清楚拼接思路，然后不就是取余嘛。

以直代曲+正向遍历

// 拼接法处理循环数组
public int[] nextGreaterElements(int[] nums) {
  // 复制并拼接
  int[] numsNew = new int[nums.length * 2];
  int[] numsRes = new int[numsNew.length];
  for (int i = 0; i < numsNew.length; i++) {
    numsNew[i] = nums[i % nums.length];
  }
  // 单调栈处理+正向遍历
  Deque<Integer> monoStack = new ArrayDeque<>();
  for (int i = 0; i < numsNew.length; i++) {
    // 注意存的是索引，那么比较的时候也得小心
    while (!monoStack.isEmpty() && numsNew[monoStack.peek()] < numsNew[i]) { 
      int curr = monoStack.poll();
      numsRes[curr] = numsNew[i];
    }
    monoStack.push(i);
  }
  // bug: 之前的处理方法不对，没能算出来的是栈内遗留的
  while (!monoStack.isEmpty()) {
    numsRes[monoStack.poll()] = -1;
  }
  // Arrays.stream(numsRes).forEach(x -> System.out.print(x + " "));
  // 保留前半部分
  int[] res = Arrays.copyOfRange(numsRes, 0, nums.length);
  return res;
}

模拟拼接+反向遍历

class Solution {
  // 模拟拼接+单调栈反向遍历
  public int[] nextGreaterElements(int[] nums) {
    Deque<Integer> monoStack = new ArrayDeque<>();
    int[] ans = new int[nums.length];
    int n = nums.length * 2;  // 模拟拼接
    for (int i = n - 1; i >= 0; i--) {
      while (!monoStack.isEmpty() && monoStack.peek() <= nums[i % nums.length]) {
        monoStack.pop();
      }
      ans[i % nums.length] = monoStack.isEmpty() ? -1 : monoStack.peek();
      monoStack.push(nums[i % nums.length]);
    }
    return ans;
  }
}

柱状图中最大的矩形

固定高，找宽度，找的过程中有些东西可以保存下来，用单调栈优化，可以迅速找到左边比出栈元素小于等于的第一个元素，这样左边就直接找到了O(1)的复杂度找到了，右边的当前元素又正好是小于的，于是宽度就确定了。即使是等于也会出栈直到小于。这是正向遍历，比较好理解。反向遍历其实也差不多。

class Solution {
  public int largestRectangleArea(int[] heights) {
    // 引入哨兵机制，简化最左边，最右边的判断
    int[] heights_dummy = new int[heights.length + 2];
    heights_dummy[0] = 0;
    heights_dummy[heights.length + 1] = 0;
    int i = 1;
    for (int x : heights) {
      heights_dummy[i++] = x;
    }
    // 单调栈法 找出栈元素左边第一个比它小的元素，存索引
    Deque<Integer> stack = new ArrayDeque<>();
    int max = 0;
    for (i = 0; i < heights_dummy.length; i++) {
      while (!stack.isEmpty() && heights_dummy[stack.peek()] > heights_dummy[i]) {  // bug: 高度相比，切记存的是索引
        int h = stack.pop(); // 当前的高度所在的索引
        int left = stack.peek();  // 左边第一个比出栈元素小的索引
        max = Math.max(max, (i - left - 1) * heights_dummy[h]);
      }
      // 相等的柱子其实不用判断，对结果没有什么影响
      stack.push(i);  // 存索引
    }
    return max;
  }
}

模板（正向遍历逆向思维）

public int[] dailyTemperatures(int[] nums) {
  // 用栈来保存当前没法算出来的数组的索引
  // 用栈来保存过去的信息，这是一个单调不增栈，能找到过去比当前元素小的
  LinkedList<Integer> stack = new LinkedList<>();
  int[] result = new int[nums.length];
  for (int i = 0; i < nums.length; i++) {
    while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
      int prev = stack.pop();
      result[prev] = i - prev;
    }
    stack.push(i);
  }
  return result;
}

模板（反向遍历正向思维）

public int[] dailyTemperatures(int[] nums) {
  // 用栈来保存过去的信息，这是一个单调不减栈，能找到第一个比当前元素大的
  Deque<Integer> stack = new ArrayDeque<>();
  int[] ans = new int[nums.length];
  for (int i = nums.length - 1; i >= 0; i--) {
    while (!stack.isEmpty() && nums[i] >= nums[stack.peek()]) {
      stack.pop();  // 已经有更大的了，过去的小个子统统滚出去，别浪费空间
    }
    ans[i] = stack.isEmpty() ? 0 : stack.peek() - i;   // 直接得比当前元素更大的第一个元素
    stack.push(i);
  }
  return ans;
}

单调栈

陈述