【LeetCode】升级打怪之路 Day 11：栈的应用、单调栈

今日题目：

• Problem 1: 栈的应用
  • 155. 最小栈 | LeetCode
  • 20. 有效的括号 | LeetCode
  • 150. 逆波兰表达式求值 | LeetCode
• Problem 2: 单调栈
  • 496. 下一个更大元素 I
  • 739. 每日温度
  • 503. 下一个更大元素 II

今天主要学习了栈的一些应用和单调栈。

• 栈的基本应用已经学习过很多次了，像括号匹配等问题，比较熟悉了，所以难度不大。
• 单调栈比较重要，它解决了“寻找每个元素的下一个更大元素”这个基本问题。我们要学会解决这个基本问题的代码思路，并将其通过转化来解决具体问题。

所以，单调栈是今天的重点，要学会其解决“寻找下一个更大元素”这个基本问题的思路，再学习如何将其用于解决具体问题。

Problem 1：栈 - “先进后出”的应用

LC 155. 最小栈 【easy】

155. 最小栈 | LeetCode

这个题目做过多次了，难度不大。

LC 20. 有效的括号 【easy】

20. 有效的括号 | LeetCode

括号匹配是使用栈解决的经典问题。通过这个题，可以学会如何灵活运用 stack 来解决这个问题。

LC 150. 逆波兰表达式求值 【easy】

150. 逆波兰表达式求值 | LeetCode

也是一个栈的经典应用，难度不大（也可能是写过好几次了）。

Problem 2：单调栈 【必会】

单调栈用于解决找下一个更大元素的问题。这是 LeetCode 中一类经典问题。学会的话就不难，没学的话一时也不太好想到思路。

首先需要学会使用单调栈的基本模板，然后再学习如何利用它解决具体的问题。

✴️ 单调栈解决的基本问题：找下一个更大元素 【classic】

参考 单调栈结构解决三道算法题 | labuladong

首先明确单调栈所能解决的基本问题：给一个数组 A，找出其中每个元素的右边的下一个更大元素。比如 A = [5, 1, 7]，那么结果就是 answer = [7, 7, -1]，因为 5 和 1 的下一个更大元素都是 7，而 7 没有下一个更大元素，于是填充 -1 作为特殊值。当然，answer 中的值也可以是 A 的下标索引，这样就是 answer = [2, 2, -1]，因为 A[0] 和 A[1] 的下一个更大元素的索引都是 2，所以 answer[0] 和 answer[1] 都是 2。

解决的思想是，假设每个元素的值就是这个元素的身高，让每个元素向后看，比自己矮的都身高不够，而第一个露出头来比自己高的那个元素就是答案，比如下图：

图片来自 labuladong

那寻找 answer 的方法，从代码上实现思路就是：声明一个 stack，从后向前遍历 nums，每次元素入栈前，把栈顶上挤压掉身高小于等于自己的元素，然后记录下栈顶（也就是 nums[i] 身后更大的元素），接着入栈，继续下一轮循环，直到遍历 nums 结束。代码如下：

int[] findNextLarger(int[] nums) {int[] nextLarger = new int[nums.length];  // 存放 answerList<Integer> stack = new ArrayList<>();  // 单调栈// 从后向前遍历 numsfor (int i = nums.length - 1; i >= 0; i--) {// 挤压掉身高小于等于自己的元素while (!stack.isEmpty() && stack.getLast() <= nums[i]) {stack.removeLast();}// 记录栈顶元素作为 nums[i] 身后的更大元素nextLarger[i] = stack.isEmpty()? -1: stack.getLast();// 入栈nextLarger.addLast(nums[i]);} return nextLarger;
}

这个问题中，每个元素都被 push 一次，最多被 pop 一次，所以复杂度是 $O(n)$。

有了解决这个基本问题的代码模板，我们就可以用这个单调栈的思路来解决一些具体的问题了。

LC 496. 下一个更大元素 I

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

学会了上面的基本代码模板，解决这个问题就会容易很多了。

这个题目的特殊之处在于，我们需要找 nums2 的子集 nums1 在 nums2 中的下一个更大元素，所以我们对 nums2 使用之前的方法来得到 nextLarger 数组，然后需要再将其转换为 map，记录着 元素 -> 下一个更大元素 的映射，然后 nums1 就可以使用这个 map 进行检索从而得到答案。

代码如下图：

可以看出来，解决这个问题的关键还是使用单调栈。

LC 739. 每日温度

739. 每日温度 | LeetCode

这也是对基本问题的一个变形，我们再 nextLarger 中需要存的不是下一个更大的元素，而是下一个更大元素的索引下标，这样才能计算出索引下标的差值。学会基本问题之后，难度也不大。

LC 503. 下一个更大元素 II 【稍有难度】

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

这也是一个基本问题的变形，基本问题中，nums 是一个普通数组，而这个题将 nums 定义为一种环形数组。

面对这种需求，常用套路就是将数组长度翻倍：

实现这种“翻倍”的效果的方式，可以构造新数组、可以利用循环数组的技巧（取模）、可以两次循环等等，都可以。

单调栈问题总结

我们学会了单调栈解决“下一个更大元素”这个基本问题的解题方法，但在实际应用中，题目往往会更加复杂一些，这时我们需要把具体问题转化为单调栈相关问题来解决。