栈

在 单调栈实践（一）：入门 中对单调栈做了一个初步介绍，同时使用一个类似单调栈的题目做了入门的尝试。在本文中，将分析正式单调栈的使用案例。 实践： LeetCode 503. 下一个更大元素 II 单调栈主要就是为了解决选择下一个更大或者更小元素的相关问题。来看一下 LeetCode 503. 下一个更大元素 II。 给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的下一个更大元素。 数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。 如果熟悉单调栈，这道题的解法就一目了然：将数组从后向前遍历，如果单调栈栈顶元素比当前元素小，就将栈顶元素弹出；重复上述操作，直到栈顶元素大于当前元素，或者栈为空。如果栈不为空，则栈顶元素就是当前元素的后继更大元素。代码如下： /** * LeetCode 503. 下一个更大元素 II * * @author D瓜哥 · https://www.diguage.com * @since 2024-07-05 23:08:39 */ public int[] nextGreaterElements(int[] nums) { if (nums == null || nums.length == 0) { return nums; } int[] result = new int[nums.length]; Deque<Integer> stack = new LinkedList<>(); // 只需要将数组“拼接”，遍历两遍数组，就可以解决所有元素后继更大元素的问题 // 从后向前遍历，再加上单调递增栈，就是时间复杂度为 O(n) 的解决方案 for (int i = 2 * nums.length - 1; i >= 0; i--) { // 取余即可获取当前需要处理的元素 int index = i % nums.length; // 在单调栈不为空的情况下，将栈中小于等于当前元素的值都弹出 while (!stack.isEmpty() && stack.peek() <= nums[index]) { stack.pop(); } // 剩下元素既是比当前元素大的后继元素。为空则是没有更大元素 // 这里还有一个隐含变量： // 由于栈是从后向前添加，则栈顶元素距离当前元素更近。 // 如果栈不为空，则栈顶元素就是符合条件的元素。 result[index] = stack.isEmpty() ? -1 : stack.peek(); stack.push(nums[index]); } return result; } 使用单调栈，一个关键点是确定使用的是单调递增栈，还是单调递减栈。 这里给大家留一个思考题：本文提供的答案是从后向前遍历数组。尝试一下从前向后遍历数组的解决方案。 实践： LeetCode 42. 接雨水 下面再来看一下： LeetCode 42. 接雨水。 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

最近刷 LeetCode 算法题中，遇到了一些需要单调栈的题目，就顺便学习了一下单调栈。分享出来，以备后续深入学习。 学习单调栈之前，先了解一些栈。 栈 Stack 栈是一个众所周知的线性数据结构，它遵循先入后出（First In Last Out，简称 FILO）或后入先出（Last In First Out，简称 LIFO）的访问顺序。操作示意图如下： 图 1. 入栈与出栈 单调栈 Monotonic Stack 单调栈是一种特殊的栈，添加了一些限制条件：内部元素只能是递增或递减的顺序存储；添加元素时，如果新元素不符合单调性，则将其内部元素弹出，直到符合添加时，才添加元素。根据元素顺序，又可分为单调递增栈和单调递减栈。操作示意图如下： 图 2. 单调递增栈 图 3. 单调递减栈 代码示例 在写代码时，一般基于 Deque 来实现，通常用到以下四个方法： deque.isEmpty()：如果 deque 不包含任何元素，则返回 true，否则返回 false。因为要栈顶元素在满足要求的时候要弹出，所以需要进行空栈判断。有些场景，可能栈一定不会空的时候，就不需要该方法进行空栈判断。 deque.push(e)：将元素 e 入栈。 deque.pop()：将栈顶元素弹出，并返回当前弹出的栈顶元素。 deque.peek()：获取栈顶元素，不弹出。 // 定义一个单调栈 Deque<Integer> stack = new LinkedList<>(); // 第一个元素，直接添加 stack.push(0); // 这里存的是数组下标 for (int i = 1; i < nums.length; i++) { // 单调递增栈这里就是大于，即 nums[i] > nums[deque.peek()] if (nums[i] < nums[stack.peek()]) { stack.push(i); } else if (nums[i] == nums[stack.peek()]) { stack.push(i); // 此处除了入栈，在有些场景下，还有可能有其他操作 // .............. } else { // 循环比较，直到遇到当前元素小于栈顶的元素情况，跳出循环 // 单调递增栈，这里是小于，即nums[i] < nums[deque.peek()] while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) { //主要逻辑 // ............ // ............ // 弹出栈顶元素 stack.pop(); } stack.push(i); } } 应用： LeetCode 155. 最小栈 来看一个 LeetCode 算法提： LeetCode 155. 最小栈，D瓜哥愿意称之为单调栈入门最佳试题。