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

今日题目：

Problem 1: 栈的应用
155. 最小栈 | LeetCode
20. 有效的括号 | LeetCode
150. 逆波兰表达式求值 | LeetCode

Problem 2: 单调栈
496. 下一个更大元素 I
739. 每日温度
503. 下一个更大元素 II

- Problem 1：栈 - “先进后出”的应用
- - LC 155. 最小栈【easy】
  - LC 20. 有效的括号【easy】
  - LC 150. 逆波兰表达式求值【easy】
- Problem 2：单调栈【必会】
- - ✴️ 单调栈解决的基本问题：找下一个更大元素【classic】
  - LC 496. 下一个更大元素 I
  - LC 739. 每日温度
  - LC 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];  // 存放 answer
	List<Integer> stack = new ArrayList<>();  // 单调栈
	
	// 从后向前遍历 nums
	for (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 进行检索从而得到答案。

代码如下图：

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