1. 单调栈算法竞赛与面试中的高效解题利器在算法竞赛和编程面试中单调栈是一种极其高效且实用的数据结构。它通过维护栈内元素的单调性能够在O(n)时间复杂度内解决一系列看似复杂的问题。我第一次接触单调栈是在解决LeetCode第84题柱状图中最大的矩形时当时暴力解法超时让我意识到必须寻找更优解而单调栈正是那把钥匙。单调栈的核心思想很简单在遍历数组时维护一个栈结构保证栈内元素始终保持单调递增或单调递减的顺序。这种结构特别适合解决寻找下一个更大/更小元素这类问题。在实际应用中单调栈可以高效解决四大类问题寻找下一个更大/更小元素计算柱状图最大矩形面积处理滑动窗口极值问题解决某些特殊的动态规划问题2. 单调栈的核心原理与实现步骤2.1 单调栈的基本性质单调栈有两种基本形式单调递增栈栈底到栈顶元素值递增单调递减栈栈底到栈顶元素值递减选择哪种单调性取决于具体问题当需要找下一个更大元素时使用单调递增栈当需要找下一个更小元素时使用单调递减栈关键提示单调栈中通常存储数组索引而非元素值因为索引可以同时提供位置和值信息这在计算距离、面积等问题时非常有用。2.2 单调栈的通用实现模板以下是单调栈的Python通用实现模板def monotonic_stack(nums): stack [] # 存储索引 result [0] * len(nums) # 存储结果 for i in range(len(nums)): # 维护栈的单调性 while stack and nums[i] nums[stack[-1]]: # 这里决定递增/递减 top_idx stack.pop() # 处理弹出的元素 result[top_idx] i - top_idx # 根据问题调整 stack.append(i) # 处理栈中剩余元素 while stack: top_idx stack.pop() result[top_idx] -1 # 或根据问题需求赋值 return result2.3 单调栈的四步解题法根据多年刷题经验我总结出使用单调栈的四步解题法确定栈的单调性明确问题要找的是更大还是更小元素找更大元素→单调递增栈找更小元素→单调递减栈确定栈中存储内容90%情况下存储索引更优特殊情况下可能需要存储值或复合数据设计弹栈处理逻辑这是解题的核心不同问题处理方式不同可能需要计算距离、面积、或更新结果数组处理剩余元素遍历结束后栈中可能还有未处理元素根据问题要求给这些元素赋默认值3. 经典问题实战解析3.1 下一个更大元素问题LeetCode #496问题重述给定两个数组nums1和nums2其中nums1是nums2的子集。对于nums1中的每个元素找到它在nums2中对应位置右侧的第一个更大元素。解法分析这道题有两种解法暴力法时间复杂度O(m*n)单调栈法时间复杂度O(mn)单调栈解法思路预处理nums2使用单调栈找到每个元素的下一个更大元素将结果存入哈希表便于快速查询遍历nums1直接从哈希表获取结果优化后的代码实现class Solution: def nextGreaterElement(self, nums1: List[int], nums2: List[int]) - List[int]: stack [] next_greater {} # 逆序遍历更容易理解 for num in reversed(nums2): while stack and num stack[-1]: stack.pop() next_greater[num] stack[-1] if stack else -1 stack.append(num) return [next_greater[num] for num in nums1]复杂度分析时间复杂度O(mn)其中m是nums1长度n是nums2长度空间复杂度O(n)用于存储哈希表和栈3.2 每日温度问题LeetCode #739问题重述给定每日温度数组返回一个数组表示需要等待多少天才能遇到更高温度。解法分析这是典型的下一个更大元素变种需要计算的是天数差而非元素值。关键点使用单调递减栈栈中存储索引以便计算天数差遇到更高温度时更新结果数组代码实现与注释class Solution: def dailyTemperatures(self, T: List[int]) - List[int]: n len(T) res [0] * n stack [] # 存储索引 for i in range(n): # 当前温度比栈顶温度高时 while stack and T[i] T[stack[-1]]: prev_idx stack.pop() res[prev_idx] i - prev_idx # 计算天数差 stack.append(i) return res实战技巧逆序遍历也可以解决这个问题但正序更直观初始化结果数组为0这样未处理的元素自动为0存储索引而非温度值便于计算天数差3.3 柱状图中最大矩形LeetCode #84问题重述给定柱状图的高度数组求能勾勒出的最大矩形面积。解法分析这是单调栈的经典应用关键在于找到每根柱子左右第一个比它矮的柱子。解题思路使用单调递增栈遍历时维护栈的递增性当遇到较矮柱子时计算弹出柱子的最大面积面积计算公式高度×宽度(右边界-左边界-1)优化后的代码实现class Solution: def largestRectangleArea(self, heights: List[int]) - int: heights [0] heights [0] # 添加哨兵 stack [] max_area 0 for i in range(len(heights)): while stack and heights[i] heights[stack[-1]]: h heights[stack.pop()] w i - stack[-1] - 1 max_area max(max_area, h * w) stack.append(i) return max_area关键优化点添加哨兵节点简化边界处理一次遍历同时确定左右边界在弹栈时即时计算面积经验分享这个问题我最初用暴力法提交时超时了后来发现单调栈解法的时间复杂度从O(n²)降到O(n)性能提升显著。这也是单调栈强大之处的典型例证。4. 单调栈的高级应用与技巧4.1 处理环形数组问题有些问题如LeetCode #503下一个更大元素II涉及环形数组。解决方法是将数组翻倍然后用单调栈处理。class Solution: def nextGreaterElements(self, nums: List[int]) - List[int]: n len(nums) res [-1] * n stack [] for i in range(2 * n): while stack and nums[i % n] nums[stack[-1]]: res[stack.pop()] nums[i % n] if i n: stack.append(i) return res4.2 二维矩阵中的单调栈应用单调栈也可以扩展到二维问题如LeetCode #85最大矩形。解法是将二维问题转化为一系列柱状图问题然后使用单调栈求解。4.3 常见错误与调试技巧在实现单调栈时容易犯以下错误混淆单调递增和单调递减栈忘记处理栈中剩余元素边界条件处理不当如空栈访问调试建议打印栈状态和中间结果用小例子手动模拟算法过程特别注意索引越界问题5. 单调栈的复杂度分析与适用场景5.1 时间复杂度分析单调栈的典型时间复杂度为O(n)因为每个元素最多入栈一次、出栈一次即使有嵌套循环总操作次数也是2n次5.2 空间复杂度分析空间复杂度一般为O(n)主要用于存储栈结构存储结果数组5.3 适用问题特征适合用单调栈解决的问题通常具有以下特征需要寻找下一个更大/更小元素需要计算基于元素位置的面积或距离问题可以转化为寻找边界的问题5.4 不适用场景以下情况可能不适合使用单调栈需要随机访问历史数据问题与元素顺序无关数据量非常小暴力法足够6. 单调栈的变种与扩展6.1 单调队列单调队列是单调栈的扩展可以在两端操作适用于滑动窗口问题。6.2 带权值的单调栈某些问题需要在栈中存储额外信息如累积和或其他统计量。6.3 多维度单调栈处理更复杂的问题时可能需要同时维护多个单调栈。在实际刷题过程中我发现单调栈的掌握需要大量练习。建议从简单题开始逐步过渡到难题同时注意总结各类问题的共性和特性。我个人的练习路线是#496 → #739 → #503 → #84 → #85由浅入深循序渐进。
1. 单调栈算法竞赛与面试中的高效解题利器在算法竞赛和编程面试中单调栈是一种极其高效且实用的数据结构。它通过维护栈内元素的单调性能够在O(n)时间复杂度内解决一系列看似复杂的问题。我第一次接触单调栈是在解决LeetCode第84题柱状图中最大的矩形时当时暴力解法超时让我意识到必须寻找更优解而单调栈正是那把钥匙。单调栈的核心思想很简单在遍历数组时维护一个栈结构保证栈内元素始终保持单调递增或单调递减的顺序。这种结构特别适合解决寻找下一个更大/更小元素这类问题。在实际应用中单调栈可以高效解决四大类问题寻找下一个更大/更小元素计算柱状图最大矩形面积处理滑动窗口极值问题解决某些特殊的动态规划问题2. 单调栈的核心原理与实现步骤2.1 单调栈的基本性质单调栈有两种基本形式单调递增栈栈底到栈顶元素值递增单调递减栈栈底到栈顶元素值递减选择哪种单调性取决于具体问题当需要找下一个更大元素时使用单调递增栈当需要找下一个更小元素时使用单调递减栈关键提示单调栈中通常存储数组索引而非元素值因为索引可以同时提供位置和值信息这在计算距离、面积等问题时非常有用。2.2 单调栈的通用实现模板以下是单调栈的Python通用实现模板def monotonic_stack(nums): stack [] # 存储索引 result [0] * len(nums) # 存储结果 for i in range(len(nums)): # 维护栈的单调性 while stack and nums[i] nums[stack[-1]]: # 这里决定递增/递减 top_idx stack.pop() # 处理弹出的元素 result[top_idx] i - top_idx # 根据问题调整 stack.append(i) # 处理栈中剩余元素 while stack: top_idx stack.pop() result[top_idx] -1 # 或根据问题需求赋值 return result2.3 单调栈的四步解题法根据多年刷题经验我总结出使用单调栈的四步解题法确定栈的单调性明确问题要找的是更大还是更小元素找更大元素→单调递增栈找更小元素→单调递减栈确定栈中存储内容90%情况下存储索引更优特殊情况下可能需要存储值或复合数据设计弹栈处理逻辑这是解题的核心不同问题处理方式不同可能需要计算距离、面积、或更新结果数组处理剩余元素遍历结束后栈中可能还有未处理元素根据问题要求给这些元素赋默认值3. 经典问题实战解析3.1 下一个更大元素问题LeetCode #496问题重述给定两个数组nums1和nums2其中nums1是nums2的子集。对于nums1中的每个元素找到它在nums2中对应位置右侧的第一个更大元素。解法分析这道题有两种解法暴力法时间复杂度O(m*n)单调栈法时间复杂度O(mn)单调栈解法思路预处理nums2使用单调栈找到每个元素的下一个更大元素将结果存入哈希表便于快速查询遍历nums1直接从哈希表获取结果优化后的代码实现class Solution: def nextGreaterElement(self, nums1: List[int], nums2: List[int]) - List[int]: stack [] next_greater {} # 逆序遍历更容易理解 for num in reversed(nums2): while stack and num stack[-1]: stack.pop() next_greater[num] stack[-1] if stack else -1 stack.append(num) return [next_greater[num] for num in nums1]复杂度分析时间复杂度O(mn)其中m是nums1长度n是nums2长度空间复杂度O(n)用于存储哈希表和栈3.2 每日温度问题LeetCode #739问题重述给定每日温度数组返回一个数组表示需要等待多少天才能遇到更高温度。解法分析这是典型的下一个更大元素变种需要计算的是天数差而非元素值。关键点使用单调递减栈栈中存储索引以便计算天数差遇到更高温度时更新结果数组代码实现与注释class Solution: def dailyTemperatures(self, T: List[int]) - List[int]: n len(T) res [0] * n stack [] # 存储索引 for i in range(n): # 当前温度比栈顶温度高时 while stack and T[i] T[stack[-1]]: prev_idx stack.pop() res[prev_idx] i - prev_idx # 计算天数差 stack.append(i) return res实战技巧逆序遍历也可以解决这个问题但正序更直观初始化结果数组为0这样未处理的元素自动为0存储索引而非温度值便于计算天数差3.3 柱状图中最大矩形LeetCode #84问题重述给定柱状图的高度数组求能勾勒出的最大矩形面积。解法分析这是单调栈的经典应用关键在于找到每根柱子左右第一个比它矮的柱子。解题思路使用单调递增栈遍历时维护栈的递增性当遇到较矮柱子时计算弹出柱子的最大面积面积计算公式高度×宽度(右边界-左边界-1)优化后的代码实现class Solution: def largestRectangleArea(self, heights: List[int]) - int: heights [0] heights [0] # 添加哨兵 stack [] max_area 0 for i in range(len(heights)): while stack and heights[i] heights[stack[-1]]: h heights[stack.pop()] w i - stack[-1] - 1 max_area max(max_area, h * w) stack.append(i) return max_area关键优化点添加哨兵节点简化边界处理一次遍历同时确定左右边界在弹栈时即时计算面积经验分享这个问题我最初用暴力法提交时超时了后来发现单调栈解法的时间复杂度从O(n²)降到O(n)性能提升显著。这也是单调栈强大之处的典型例证。4. 单调栈的高级应用与技巧4.1 处理环形数组问题有些问题如LeetCode #503下一个更大元素II涉及环形数组。解决方法是将数组翻倍然后用单调栈处理。class Solution: def nextGreaterElements(self, nums: List[int]) - List[int]: n len(nums) res [-1] * n stack [] for i in range(2 * n): while stack and nums[i % n] nums[stack[-1]]: res[stack.pop()] nums[i % n] if i n: stack.append(i) return res4.2 二维矩阵中的单调栈应用单调栈也可以扩展到二维问题如LeetCode #85最大矩形。解法是将二维问题转化为一系列柱状图问题然后使用单调栈求解。4.3 常见错误与调试技巧在实现单调栈时容易犯以下错误混淆单调递增和单调递减栈忘记处理栈中剩余元素边界条件处理不当如空栈访问调试建议打印栈状态和中间结果用小例子手动模拟算法过程特别注意索引越界问题5. 单调栈的复杂度分析与适用场景5.1 时间复杂度分析单调栈的典型时间复杂度为O(n)因为每个元素最多入栈一次、出栈一次即使有嵌套循环总操作次数也是2n次5.2 空间复杂度分析空间复杂度一般为O(n)主要用于存储栈结构存储结果数组5.3 适用问题特征适合用单调栈解决的问题通常具有以下特征需要寻找下一个更大/更小元素需要计算基于元素位置的面积或距离问题可以转化为寻找边界的问题5.4 不适用场景以下情况可能不适合使用单调栈需要随机访问历史数据问题与元素顺序无关数据量非常小暴力法足够6. 单调栈的变种与扩展6.1 单调队列单调队列是单调栈的扩展可以在两端操作适用于滑动窗口问题。6.2 带权值的单调栈某些问题需要在栈中存储额外信息如累积和或其他统计量。6.3 多维度单调栈处理更复杂的问题时可能需要同时维护多个单调栈。在实际刷题过程中我发现单调栈的掌握需要大量练习。建议从简单题开始逐步过渡到难题同时注意总结各类问题的共性和特性。我个人的练习路线是#496 → #739 → #503 → #84 → #85由浅入深循序渐进。
