1. 题目背景与核心思路LeetCode 496题下一个更大元素 I是单调栈算法的经典入门题目。题目给定两个没有重复元素的数组nums1和nums2其中nums1是nums2的子集。要求找出nums1中每个元素在nums2中对应位置的下一个更大元素。这个问题的关键在于理解下一个更大元素的定义对于nums2中的一个元素x其下一个更大元素是x右侧第一个比x大的元素。如果不存在这样的元素则输出-1。例如输入nums1 [4,1,2], nums2 [1,3,4,2]输出[-1,3,-1]解释数字4在nums2中没有下一个更大元素所以输出-1数字1的下一个更大元素是3数字2在nums2中没有下一个更大元素所以输出-12. 暴力解法与复杂度分析最直观的解法是暴力双重循环遍历nums1中的每个元素在nums2中找到该元素的位置从该位置开始向右扫描找到第一个更大的元素Python实现代码def nextGreaterElement(nums1, nums2): result [] for num in nums1: index nums2.index(num) found -1 for i in range(index1, len(nums2)): if nums2[i] num: found nums2[i] break result.append(found) return result时间复杂度分析外层循环遍历nums1O(m)index()操作O(n)内层查找下一个更大元素最坏O(n)总时间复杂度O(m*n)空间复杂度O(1)不考虑输出结果的空间这种解法在小规模数据上可行但当数组长度较大时如n10^5性能会急剧下降。3. 单调栈优化解法单调栈是解决下一个更大元素类问题的标准解法可以将时间复杂度优化到O(n)。3.1 单调栈核心思想单调栈维护一个栈结构保证栈内元素从栈底到栈顶是单调递减的。处理每个元素时当前元素 栈顶元素直接入栈当前元素 栈顶元素不断弹出栈顶元素直到满足单调性同时记录这些被弹出元素的下一个更大元素就是当前元素这种方法的精妙之处在于每个元素最多入栈和出栈各一次在出栈时就能确定其下一个更大元素最终留在栈中的元素就是没有下一个更大元素的3.2 具体实现步骤使用哈希表记录nums2中每个元素的下一个更大元素初始化一个空栈和空哈希表遍历nums2中的每个元素while栈不为空且当前元素 栈顶元素弹出栈顶元素并在哈希表中记录其下一个更大元素为当前元素将当前元素压入栈中遍历nums1从哈希表中查询结果Python实现代码def nextGreaterElement(nums1, nums2): stack [] mapping {} for num in nums2: while stack and num stack[-1]: mapping[stack.pop()] num stack.append(num) # 栈中剩余元素没有下一个更大元素 while stack: mapping[stack.pop()] -1 return [mapping[num] for num in nums1]3.3 复杂度分析时间复杂度遍历nums2构建哈希表O(n)遍历nums1查询结果O(m)总时间复杂度O(m n)空间复杂度栈空间最坏O(n)哈希表O(n)总空间复杂度O(n)4. 算法优化与边界处理4.1 空间优化技巧可以进一步优化空间使用在构建哈希表的同时处理nums1def nextGreaterElement(nums1, nums2): stack [] mapping {} for num in nums2: while stack and num stack[-1]: mapping[stack.pop()] num stack.append(num) # 直接处理nums1不需要先处理栈中剩余元素 return [mapping.get(num, -1) for num in nums1]这种写法利用了Python字典的get方法对于没有在mapping中的key即没有下一个更大元素的直接返回-1。4.2 边界条件处理需要考虑的特殊情况空数组输入应返回空列表nums1包含nums2中没有的元素根据题意nums1是nums2的子集所以理论上不会出现重复元素题目已说明所有元素都是唯一的防御性代码示例def nextGreaterElement(nums1, nums2): if not nums1 or not nums2: return [] 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]5. 单调栈的变种与应用5.1 相关LeetCode题目单调栈可以解决一系列类似问题下一个更大元素 II循环数组下一个更大元素 III数字重组每日温度柱状图中最大的矩形接雨水5.2 循环数组的处理对于循环数组即最后一个元素的下一个元素是第一个元素可以通过将数组长度翻倍来模拟循环def nextGreaterElements(nums): 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 res5.3 实际应用场景单调栈在以下场景中有重要应用股票价格分析寻找下一个更高价格编译器优化寄存器分配数据库查询优化范围查询图形处理寻找轮廓线6. 常见错误与调试技巧6.1 新手常见错误栈空判断遗漏在while循环中忘记检查stack是否为空元素相等处理题目要求严格大于所以等于的情况不应弹出哈希表初始化忘记处理栈中剩余元素索引混淆在处理循环数组时容易搞混原始索引和扩展后的索引6.2 调试方法打印中间状态在循环中打印栈和哈希表的状态for num in nums2: print(fProcessing {num}, stack: {stack}, mapping: {mapping}) while stack and num stack[-1]: popped stack.pop() mapping[popped] num print(fPopped {popped}, mapped to {num}) stack.append(num)小规模测试用例使用简单例子手动验证nums1 [2,4] nums2 [1,2,3,4]边界测试空数组、单元素数组、完全递减数组等7. 算法扩展与思考7.1 双向处理除了从左到右处理也可以考虑从右到左处理def nextGreaterElement(nums1, nums2): stack [] mapping {} for num in reversed(nums2): while stack and num stack[-1]: stack.pop() mapping[num] stack[-1] if stack else -1 stack.append(num) return [mapping[num] for num in nums1]7.2 并行计算优化对于大规模数据可以考虑分块处理数组使用多线程或GPU加速预处理和缓存常用查询7.3 进阶思考题如果允许重复元素算法应该如何修改如何同时找到上一个更小和下一个更大的元素如何扩展到多维数据