1. 单调栈基础概念解析单调栈Monotonic Stack是一种特殊的栈结构它在算法题解中经常被用来处理下一个更大元素这类问题。我第一次接触这个概念是在解决LeetCode第496题时当时被它的巧妙设计所震撼。单调栈的核心特性在于栈内元素始终保持单调递增或单调递减的顺序。这种特性使得它能够高效解决一类特定问题——寻找序列中每个元素左右两侧第一个满足某种条件的相邻元素。注意单调栈并非一种独立的数据结构而是对普通栈的一种使用约束。关键在于维护栈内元素的单调性。举个例子假设我们需要找数组中每个元素右边第一个比它大的数。使用单调递减栈时当遇到比栈顶大的元素就可以确定这个元素就是栈顶元素的下一个更大元素。这个过程的时间复杂度是O(n)因为每个元素最多入栈和出栈一次。2. 单调栈的两种基本类型2.1 单调递增栈单调递增栈要求栈内元素从栈底到栈顶保持递增顺序。这种栈常用于解决寻找左边/右边第一个更小元素的问题。实现模板stack [] for num in nums: while stack and stack[-1] num: # 出栈并处理 top stack.pop() # 处理逻辑... stack.append(num)2.2 单调递减栈单调递减栈则要求栈内元素从栈底到栈顶保持递减顺序。它更适合处理寻找左边/右边第一个更大元素的问题。实现模板stack [] for num in nums: while stack and stack[-1] num: # 出栈并处理 top stack.pop() # 处理逻辑... stack.append(num)在实际应用中选择哪种单调栈取决于具体问题需求。我通常会先明确要找的是更大还是更小的元素再决定使用哪种单调性。3. 单调栈的典型应用场景3.1 下一个更大元素问题这是单调栈最经典的应用场景。以LeetCode 496题为例给定两个数组nums1和nums2其中nums1是nums2的子集要求找出nums1中每个元素在nums2中对应位置的右边第一个更大的元素。解决方案def nextGreaterElement(nums1, nums2): stack [] mapping {} for num in nums2: while stack and num stack[-1]: mapping[stack.pop()] num stack.append(num) return [mapping.get(num, -1) for num in nums1]3.2 柱状图中的最大矩形LeetCode 84题是另一个经典应用。给定n个非负整数表示柱状图的高度求柱状图中能勾勒出的最大矩形的面积。解决方案def largestRectangleArea(heights): stack [] max_area 0 heights [0] heights [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_area3.3 每日温度问题LeetCode 739题要求根据每日气温列表计算需要等待多少天才能观察到更高的温度。解决方案def dailyTemperatures(T): stack [] result [0] * len(T) for i, temp in enumerate(T): while stack and temp T[stack[-1]]: prev stack.pop() result[prev] i - prev stack.append(i) return result4. 单调栈的实现技巧与注意事项4.1 边界处理技巧在实际编码中边界条件往往是出错的高发区。我总结了几个处理技巧哨兵技巧在数组前后添加辅助元素如0可以简化边界判断栈初始化通常初始化为空但有时预先压入一个特殊元素更方便结果初始化根据问题需求结果数组可能需要初始化为特定值如-14.2 时间复杂度分析单调栈的时间复杂度通常是O(n)因为每个元素最多入栈和出栈各一次。空间复杂度取决于栈的最大深度最坏情况下也是O(n)。4.3 常见错误与调试新手常犯的错误包括混淆单调递增和递减栈的使用场景忘记处理栈中剩余元素索引计算错误特别是在处理宽度时边界条件考虑不周调试时建议打印栈的状态变化对简单测试用例手动模拟特别注意循环终止条件5. 单调栈的变种与扩展应用5.1 二维矩阵中的应用单调栈可以扩展到二维问题如最大矩形问题LeetCode 85。基本思路是将二维问题转化为一系列的一维问题然后对每一行或列应用单调栈技巧。5.2 循环数组处理对于循环数组问题如LeetCode 503可以通过将数组长度翻倍来模拟循环特性然后应用单调栈解决。解决方案def nextGreaterElements(nums): n len(nums) result [-1] * n stack [] for i in range(2 * n): while stack and nums[i % n] nums[stack[-1]]: result[stack.pop()] nums[i % n] if i n: stack.append(i) return result5.3 与动态规划结合在某些问题中单调栈可以与动态规划结合使用。例如股票跨度问题LeetCode 901通过维护单调栈来优化动态规划的计算过程。6. 实战训练建议要真正掌握单调栈光理解原理是不够的。我建议按照以下顺序进行训练基础模板题LeetCode 496, 739中等难度题LeetCode 503, 1019进阶挑战题LeetCode 84, 85变种应用题LeetCode 42, 316对于每道题建议先自己思考解法写出代码并测试对比优秀题解优化总结相似问题的模式我在刷题过程中发现单调栈的问题往往有固定的模式。一旦掌握了核心思想很多问题都能迎刃而解。关键在于识别问题是否属于寻找边界这一类然后选择合适的单调栈类型。 单调栈原理与应用：解决算法中的边界查找问题
1. 单调栈基础概念解析单调栈Monotonic Stack是一种特殊的栈结构它在算法题解中经常被用来处理下一个更大元素这类问题。我第一次接触这个概念是在解决LeetCode第496题时当时被它的巧妙设计所震撼。单调栈的核心特性在于栈内元素始终保持单调递增或单调递减的顺序。这种特性使得它能够高效解决一类特定问题——寻找序列中每个元素左右两侧第一个满足某种条件的相邻元素。注意单调栈并非一种独立的数据结构而是对普通栈的一种使用约束。关键在于维护栈内元素的单调性。举个例子假设我们需要找数组中每个元素右边第一个比它大的数。使用单调递减栈时当遇到比栈顶大的元素就可以确定这个元素就是栈顶元素的下一个更大元素。这个过程的时间复杂度是O(n)因为每个元素最多入栈和出栈一次。2. 单调栈的两种基本类型2.1 单调递增栈单调递增栈要求栈内元素从栈底到栈顶保持递增顺序。这种栈常用于解决寻找左边/右边第一个更小元素的问题。实现模板stack [] for num in nums: while stack and stack[-1] num: # 出栈并处理 top stack.pop() # 处理逻辑... stack.append(num)2.2 单调递减栈单调递减栈则要求栈内元素从栈底到栈顶保持递减顺序。它更适合处理寻找左边/右边第一个更大元素的问题。实现模板stack [] for num in nums: while stack and stack[-1] num: # 出栈并处理 top stack.pop() # 处理逻辑... stack.append(num)在实际应用中选择哪种单调栈取决于具体问题需求。我通常会先明确要找的是更大还是更小的元素再决定使用哪种单调性。3. 单调栈的典型应用场景3.1 下一个更大元素问题这是单调栈最经典的应用场景。以LeetCode 496题为例给定两个数组nums1和nums2其中nums1是nums2的子集要求找出nums1中每个元素在nums2中对应位置的右边第一个更大的元素。解决方案def nextGreaterElement(nums1, nums2): stack [] mapping {} for num in nums2: while stack and num stack[-1]: mapping[stack.pop()] num stack.append(num) return [mapping.get(num, -1) for num in nums1]3.2 柱状图中的最大矩形LeetCode 84题是另一个经典应用。给定n个非负整数表示柱状图的高度求柱状图中能勾勒出的最大矩形的面积。解决方案def largestRectangleArea(heights): stack [] max_area 0 heights [0] heights [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_area3.3 每日温度问题LeetCode 739题要求根据每日气温列表计算需要等待多少天才能观察到更高的温度。解决方案def dailyTemperatures(T): stack [] result [0] * len(T) for i, temp in enumerate(T): while stack and temp T[stack[-1]]: prev stack.pop() result[prev] i - prev stack.append(i) return result4. 单调栈的实现技巧与注意事项4.1 边界处理技巧在实际编码中边界条件往往是出错的高发区。我总结了几个处理技巧哨兵技巧在数组前后添加辅助元素如0可以简化边界判断栈初始化通常初始化为空但有时预先压入一个特殊元素更方便结果初始化根据问题需求结果数组可能需要初始化为特定值如-14.2 时间复杂度分析单调栈的时间复杂度通常是O(n)因为每个元素最多入栈和出栈各一次。空间复杂度取决于栈的最大深度最坏情况下也是O(n)。4.3 常见错误与调试新手常犯的错误包括混淆单调递增和递减栈的使用场景忘记处理栈中剩余元素索引计算错误特别是在处理宽度时边界条件考虑不周调试时建议打印栈的状态变化对简单测试用例手动模拟特别注意循环终止条件5. 单调栈的变种与扩展应用5.1 二维矩阵中的应用单调栈可以扩展到二维问题如最大矩形问题LeetCode 85。基本思路是将二维问题转化为一系列的一维问题然后对每一行或列应用单调栈技巧。5.2 循环数组处理对于循环数组问题如LeetCode 503可以通过将数组长度翻倍来模拟循环特性然后应用单调栈解决。解决方案def nextGreaterElements(nums): n len(nums) result [-1] * n stack [] for i in range(2 * n): while stack and nums[i % n] nums[stack[-1]]: result[stack.pop()] nums[i % n] if i n: stack.append(i) return result5.3 与动态规划结合在某些问题中单调栈可以与动态规划结合使用。例如股票跨度问题LeetCode 901通过维护单调栈来优化动态规划的计算过程。6. 实战训练建议要真正掌握单调栈光理解原理是不够的。我建议按照以下顺序进行训练基础模板题LeetCode 496, 739中等难度题LeetCode 503, 1019进阶挑战题LeetCode 84, 85变种应用题LeetCode 42, 316对于每道题建议先自己思考解法写出代码并测试对比优秀题解优化总结相似问题的模式我在刷题过程中发现单调栈的问题往往有固定的模式。一旦掌握了核心思想很多问题都能迎刃而解。关键在于识别问题是否属于寻找边界这一类然后选择合适的单调栈类型。