Python|单调栈判断132模式---算法与编程之美

问题描述

给定一个整数序列：a1, a2, ..., an，一个132模式的子序列 ai, aj, ak 被定义为：当 i < j < k 时，ai < ak < aj。设计一个算法，当给定有 n 个数字的序列时，验证这个序列中是否含有132模式的子序列。

示例1:

输入: [1, 2, 3, 4]

输出: False

解释: 序列中不存在132模式的子序列。

示例 2:

输入: [3, 1, 4, 2]

输出: True

解释: 序列中有 1 个132模式的子序列：[1, 4, 2].

解决方案

简单来说，就是在所给序列中，有没有某一个长度为3的子序列符合中间大于两边，右边大于左边。

也就是说，找到一个元素A, 在它左边有比它小的元素B，在它右边也有比它小的元素C, 并且B要小于C。

但暴力法容易超时。这里可以利用单调减栈，倒着遍历数组，当数组某个元素大于单调减栈的最大值时，这个元素就相当于A，单调减栈的最大值相当于C，而且这个C是A右边区域的最大值，更容易找到比它小的元素，接着遍历，如果出现比元素C还小的值，就找到了元素A，返回True。

代码示例：

class Solution: def find132pattern(self, nums: List[int]) -> bool: stack = [] # 设置m的初始值为负无穷 m = float('-inf') for i in range(len(nums)-1, -1, -1): if nums[i] < m: return True while stack and nums[i] > stack[-1]: m = stack.pop() stack.append(nums[i]) return False

结语

这道题给人的感觉很简单，但直接使用暴力法找所需的三个数很容易超时。这里利用的是单调减栈，这样理论上在遍历过程中可以同时找到最大的元素和右边次大的元素，如果找到了，那么接着遍历找到比右边次大的元素要小的元素是比较容易的。

END

主 编 | 王文星

责 编 | 周茂林

where2go 团队