LeetCode 132模式问题解析与单调栈解法

1. 132模式问题概述LeetCode 456题132模式是一个经典的数组模式识别问题。给定一个整数数组nums我们需要判断是否存在这样的三元组序列(i, j, k)满足i j k 且 nums[i] nums[k] nums[j]。换句话说我们需要在数组中找到三个元素它们的索引和值满足小-大-中的关系。这个问题看似简单但要想出高效的解法却需要深入思考。暴力解法的时间复杂度是O(n³)显然无法处理大规模数据。我们需要寻找更优的算法来降低时间复杂度。2. 问题分析与解法思路2.1 暴力解法分析最直观的解法是三重循环遍历所有可能的三元组组合def find132pattern(nums): n len(nums) for i in range(n): for j in range(i1, n): for k in range(j1, n): if nums[i] nums[k] nums[j]: return True return False这种解法虽然正确但时间复杂度为O(n³)在n较大时(比如n10^5)会非常低效。我们需要寻找更优的解法。2.2 优化思路我们可以从132模式的定义出发寻找更高效的解法。关键在于如何有效地记录和比较三个元素之间的关系我们需要找到nums[j] nums[k]且nums[k] nums[i]可以固定其中一个元素然后高效地寻找另外两个元素可以考虑使用单调栈来维护某些信息3. 单调栈解法详解3.1 算法思路我们可以采用单调递减栈来解决这个问题具体步骤如下从右向左遍历数组维护一个单调递减栈栈顶元素最小记录一个变量third表示可能的2元素对于当前元素nums[i]如果它大于third说明找到了132模式3.2 具体实现def find132pattern(nums): stack [] third float(-inf) for num in reversed(nums): if num third: return True while stack and stack[-1] num: third stack.pop() stack.append(num) return False3.3 算法分析时间复杂度O(n)每个元素最多入栈和出栈一次空间复杂度O(n)最坏情况下需要存储所有元素这个解法的关键在于从右向左遍历并维护一个单调递减栈。栈中存储的是可能的3元素而third变量记录的是最大的2元素。4. 其他解法探讨4.1 预处理最小值数组法另一种思路是预处理一个最小值数组记录到每个位置为止的最小值def find132pattern(nums): if len(nums) 3: return False min_left [0] * len(nums) min_left[0] nums[0] for i in range(1, len(nums)): min_left[i] min(min_left[i-1], nums[i]) stack [] for j in range(len(nums)-1, -1, -1): if nums[j] min_left[j]: while stack and stack[-1] min_left[j]: stack.pop() if stack and stack[-1] nums[j]: return True stack.append(nums[j]) return False4.2 二分查找法还可以结合二分查找来优化import bisect def find132pattern(nums): stack [] min_left [float(inf)] * len(nums) min_val nums[0] for i in range(1, len(nums)): min_left[i] min_val min_val min(min_val, nums[i]) for j in range(len(nums)-1, -1, -1): if nums[j] min_left[j]: idx bisect.bisect_left(stack, min_left[j] 1) if idx len(stack) and stack[idx] nums[j]: return True bisect.insort(stack, nums[j]) return False5. 边界条件与测试用例5.1 常见测试用例# 基本测试用例 assert find132pattern([1,2,3,4]) False assert find132pattern([3,1,4,2]) True assert find132pattern([-1,3,2,0]) True # 边界测试用例 assert find132pattern([]) False assert find132pattern([1]) False assert find132pattern([1,2]) False assert find132pattern([1,3,2]) True # 性能测试用例 large_nums list(range(10000)) [9998] assert find132pattern(large_nums) True5.2 特殊情况的处理在实际编码中需要注意以下特殊情况数组长度小于3时直接返回False数组中存在重复元素的情况数组完全升序或降序的情况数组中元素全部相同的情况6. 算法优化与变种6.1 空间优化我们可以进一步优化空间复杂度不需要存储整个min_left数组def find132pattern(nums): if len(nums) 3: return False stack [] min_left [float(inf)] * len(nums) min_val nums[0] for i in range(1, len(nums)): min_left[i] min_val min_val min(min_val, nums[i]) for j in range(len(nums)-1, -1, -1): if nums[j] min_left[j]: while stack and stack[-1] min_left[j]: stack.pop() if stack and stack[-1] nums[j]: return True stack.append(nums[j]) return False6.2 其他模式识别类似的模式识别问题还有123模式i j k且nums[i] nums[j] nums[k]321模式i j k且nums[i] nums[j] nums[k]其他组合模式这些问题的解法思路类似都可以用单调栈或预处理的方法来解决。7. 实际应用场景132模式识别虽然看似是一个抽象的算法问题但在实际中有多种应用股票交易分析可以用来识别特定的价格波动模式信号处理检测信号中的特定波形模式数据挖掘发现时间序列数据中的特定模式交易策略识别金融市场中的特定价格形态理解这类模式识别问题的解法有助于我们在实际工作中处理类似的数据分析需求。8. 解题技巧总结解决这类数组模式识别问题的通用技巧分析模式特征明确模式的具体条件和约束考虑遍历方向从左到右或从右到左选择最有利的遍历方向利用辅助数据结构栈、队列、堆等可以帮助维护中间状态预处理信息提前计算并存储一些有用信息逐步优化从暴力解法开始逐步寻找优化点对于132模式问题从右向左遍历结合单调栈是最优的解法时间复杂度O(n)空间复杂度O(n)。这种解法巧妙地利用了栈来维护可能的3元素同时通过third变量记录最大的2元素从而高效地判断是否存在满足条件的1元素。