单调栈 与 单调队列

什么是单调栈/单调队列？ 为了解决某类问题，我们需要维护一个栈/队列，保证栈或队列中的元素具有单调性。

解决什么问题呢？ 找每个元素 左边/右边 第一个比他 大/小 的元素。

例如：

• [1,2,4,3,4]中找到每个元素右边第一个比他大的元素下标，就可以使用单调栈来解决。
• [1,3,-1,-3,5,3]中找到窗口为3的每个窗口中的最大值，就可以使用单调队列。

LeetCode-单调栈

我们先解决一道经典单调栈问题，再从中总结一些规律。

LeetCode-739.每日温度

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

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

这道题实际就是找到每个元素右边第一个比他大的元素，不过要收集是下标差。

我们分析一下：

• 我们需要维护一个栈，这个栈中维护的数据应该是当前没有答案的元素。
• 栈内维护的应该是一个单调递减的序列（从栈底开始），为什么呢？单调递增那说明已经确定答案了，那就没必要存储在栈中了。
• 当遍历到一个新元素时，我们需要根栈顶元素进行比较：
  • 小于等于栈顶元素，说明此时无法决定前面任何元素的答案并且本身也是一个没有答案元素，入栈
  • 大于栈顶元素，说明此时栈顶元素将拥有答案，因此解答并将栈顶弹出，由于可能多个值都会有答案，因此这里应该是一个循环过程。本身也是一个没有答案元素，最后入栈。

再看看代码体会一下：

var dailyTemperatures = function (temperatures) {
  const res = new Array(temperatures.length).fill(0);
  const stack = [];

  for (let i = 0; i < temperatures.length; i++) {
    while (stack.length && temperatures[stack[stack.length - 1]] < temperatures[i]) {
      const index = stack.pop();
      res[index] = i - index;
    }
    stack.push(i)
  }

  return res;
};

除了我们上面分析的，代码中只有一个需要注意的：栈中存储的是每个元素在数组中的下标。

LeetCode-496.下一个更大元素 I

nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x大的元素。给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。

输入： nums1 = [4,1,2], nums2 = [1,3,4,2].
输出： [-1,3,-1]

这道题实际就是在nums2中找到每个元素的右边第一个比他大的元素。然后再根据nums1的顺序返回结果。

那很简单，实际就是在上一题的基础上，然后以nums1为顺序组织答案。暴力解法就是在nums2中找nums1每个元素对应的下标，然后再获取其下一个更大元素即可。那我们可以简化这个找的过程吗? 我的第一反应就是使用map，因为之前我们说过map可以让我们快速获知一个元素是否存在，并且可以存储额外信息，由于题目已经告知了子集关系，因此我们主要利用的是存储的额外信息。

var nextGreaterElement = function (nums1, nums2) {
  const stack = [];
  const map = new Map();

  for (let i = 0; i < nums2.length; i++) {
    while (stack && nums2[stack[stack.length - 1]] < nums2[i]) {
      const index = stack.pop();
      //将下一个更大的元素作为value
      map.set(nums2[index], nums2[i]);
    }
    stack.push(i);
  }

  const res = [];
  for (let i = 0; i < nums1.length; i++) {
    res.push(map.has(nums1[i]) ? map.get(nums1[i]) : -1);
  }
  return res;
};

LeetCode-503.下一个更大元素 II

给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。

数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。

这个题实际就是在第一题的基础上加入了“循环”，一个值的下一个更大元素可能在前面，我们实际上可以直接将这个数组复制一遍，因为找一个值的下一个更大元素，最多也只会向后多找一个数组长度而已，但是如果数组很长，这样就不好了，我们可以使用取余的操作来达到循环遍历。

先给出复制数组代码：

var nextGreaterElements = function (nums) {
  const cNums = [...nums, ...nums];
  const stack = [];
  const res = new Array(cNums.length).fill(-1);
  for (let i = 0; i < cNums.length; i++) {
    while (stack.length && cNums[i] > cNums[stack[stack.length - 1]]) {
      const index = stack.pop();
      res[index] = cNums[i];
    }
    stack.push(i);
  }

  return res.slice(0, nums.length);
};

取余代码：

var nextGreaterElements = function (nums) {
  const stack = [];
  const res = new Array(nums.length).fill(-1);
  for (let i = 0; i < nums.length * 2; i++) {
    while (stack.length && nums[i % nums.length] > nums[stack[stack.length - 1]]) {
      const index = stack.pop();
      res[index] = nums[i % nums.length];
    }
    stack.push(i % nums.length);
  }

  return res;
};

LeetCode-单调队列

目前所遇到的单调队列题目少之又少，这里举出最经典的题目，后续会慢慢补充。

LeetCode-239.滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

输入： nums = [1,3,-1,-3,5,3,6,7], k = 3
输出： [3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

在这个题中，我们使用选择队列的原因是什么？因为滑动窗口的滑动十分符合队列的出入。

分析：

• 我们需要维护的单调队列最重要的就是维护队列内元素的出入队。
• 出队：什么时候需要出队？
  • 当窗口滑动时，队头的元素需要出队
  • 当当前要入队元素大于等于队尾元素时，此时队尾元素将在后续不会使用到了，因此可以直接出队（双端队列，因此可以队尾出队操作），循环出队
• 入队：每轮遍历中，每个元素都需要入队。

var maxSlidingWindow = function (nums, k) {
  const res = [];
  //存储入队元素的下标
  const quene = [];

  for (let i = 0; i < nums.length; i++) {
    //队头元素不在窗口内时，出队
    if (quene.length && i + 1 - k > quene[0]) {
      quene.shift();
    }
    //队尾元素无用，出队
    while (quene.length && nums[i] >= nums[quene[quene.length - 1]]) {
      quene.pop();
    }
    quene.push(i);
    //每当遍历了k个元素开始，都会在每轮循环产生一个答案，队列头存储的是当前最大值
    if (i + 1 >= k) {
      res.push(nums[quene[0]]);
    }
  }
  return res;
};

总结

对于单调栈单调队列的问题，我们要清楚的是：

• 何时出入栈/队
• 单调递增还是单调递减
• 以及当前遍历元素 与 栈顶/队头元素比较 的三种情况的操作

你会发现，在单调栈问题中，我们能够使用单调栈的一个关键原因在于我们在求解一个答案时，需要使用到之前遍历的元素，从而我们使用栈来帮我们记录，并借助单调性来更好的从栈中拿到结果

后续会逐渐补充题目和进行总结，欢迎大家讨论😉