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中没有下一个更大元素，所以输出-1
2. 暴力解法与复杂度分析
最直观的解法是暴力双重循环：
- 遍历nums1中的每个元素
- 在nums2中找到该元素的位置
- 从该位置开始向右扫描，找到第一个更大的元素
Python实现代码：
def nextGreaterElement(nums1, nums2): result = [] for num in nums1: index = nums2.index(num) found = -1 for i in range(index+1, len(nums2)): if nums2[i] > num: found = nums2[i] break result.append(found) return result时间复杂度分析：
- 外层循环遍历nums1：O(m)
- index()操作：O(n)
- 内层查找下一个更大元素：最坏O(n)
- 总时间复杂度：O(m*n)
- 空间复杂度：O(1)（不考虑输出结果的空间）
这种解法在小规模数据上可行，但当数组长度较大时（如n=10^5），性能会急剧下降。
3. 单调栈优化解法
单调栈是解决"下一个更大元素"类问题的标准解法，可以将时间复杂度优化到O(n)。
3.1 单调栈核心思想
单调栈维护一个栈结构，保证栈内元素从栈底到栈顶是单调递减的。处理每个元素时：
- 当前元素 <= 栈顶元素：直接入栈
- 当前元素 > 栈顶元素：不断弹出栈顶元素，直到满足单调性，同时记录这些被弹出元素的下一个更大元素就是当前元素
这种方法的精妙之处在于：
- 每个元素最多入栈和出栈各一次
- 在出栈时就能确定其下一个更大元素
- 最终留在栈中的元素就是没有下一个更大元素的
3.2 具体实现步骤
- 使用哈希表记录nums2中每个元素的下一个更大元素
- 初始化一个空栈和空哈希表
- 遍历nums2中的每个元素：
- while栈不为空且当前元素 > 栈顶元素：
- 弹出栈顶元素，并在哈希表中记录其下一个更大元素为当前元素
- 将当前元素压入栈中
- 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 空间优化技巧
可以进一步优化空间使用，在构建哈希表的同时处理nums1：
def 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(f"Processing {num}, stack: {stack}, mapping: {mapping}") while stack and num > stack[-1]: popped = stack.pop() mapping[popped] = num print(f"Popped {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 进阶思考题
- 如果允许重复元素，算法应该如何修改？
- 如何同时找到上一个更小和下一个更大的元素？
- 如何扩展到多维数据？
