难度: Medium
给你一个整数数组 nums ，数组中共有 n 个整数。132 模式的子序列 由三个整数 nums[i]、nums[j] 和 nums[k] 组成，并同时满足：i < j < k 和 nums[i] < nums[k] < nums[j] 。
如果 nums 中存在 132 模式的子序列 ，返回 true ；否则，返回 false 。
示例 1：
输入：nums = [1,2,3,4] 输出：false 解释：序列中不存在 132 模式的子序列。
示例 2：
输入：nums = [3,1,4,2] 输出：true 解释：序列中有 1 个 132 模式的子序列： [1, 4, 2] 。
示例 3：
输入：nums = [-1,3,2,0] 输出：true 解释：序列中有 3 个 132 模式的的子序列：[-1, 3, 2]、[-1, 3, 0] 和 [-1, 2, 0] 。
提示：
n == nums.length1 <= n <= 2 * 105-109 <= nums[i] <= 109运行时间: 82 ms
内存: 32.7 MB
class Solution:
def find132pattern(self, nums: List[int]) -> bool:
stack = [] # 逆向的不严格递减栈。栈顶是答案所求的中间数
right = float('-inf')
for num in nums[::-1]:
if num < right:
return True
while stack and stack[-1] < num:
right = stack.pop()
stack.append(num)
return False
这个题解使用单调栈的思路来解决问题。从后往前遍历数组，维护一个逆向的不严格递减栈，栈顶元素代表答案中的中间数。同时用一个变量 right 记录遍历过程中遇到的最大的右边界。如果当前元素小于 right，说明找到了一个 132 模式，直接返回 True。否则，将栈中小于当前元素的数都弹出，并更新 right 为弹出的元素中的最大值，然后将当前元素压入栈中。如果遍历完整个数组都没有找到 132 模式，返回 False。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def find132pattern(self, nums: List[int]) -> bool:
stack = [] # 逆向的不严格递减栈。栈顶是答案所求的中间数
right = float('-inf') # 记录遍历过程中遇到的最大右边界
for num in nums[::-1]: # 从后往前遍历数组
if num < right: # 如果当前元素小于右边界，说明找到了 132 模式
return True
while stack and stack[-1] < num: # 将栈中小于当前元素的数都弹出
right = stack.pop() # 更新右边界为弹出的元素中的最大值
stack.append(num) # 将当前元素压入栈中
return False # 如果遍历完数组都没有找到 132 模式，返回 False
从后往前遍历数组可以有效地维护一个逆序的单调栈，这样可以更自然地处理132模式中‘3’和‘2’的关系。在这种遍历方式中，栈中存储的是候选的‘3’的值，而变量`right`则用来记录已遍历部分的最大值，即候选的‘2’。这种方法简化了逻辑，因为我们总是试图找到一个小于‘2’的数作为‘1’，这在从后向前遍历时更直观。
栈中存储的是数组中的元素本身，不是索引。这些元素代表了可能构成132模式中‘3’的候选值。通过维持一个不严格递减的栈，可以确保栈顶元素是当前遍历到的最大值，这有助于快速比较和确定是否存在一个小于此值的‘1’，从而满足132模式的条件。
‘不严格递减栈’指的是栈中的元素从栈底到栈顶是递减或相等的。这种结构是通过在遍历过程中，只有当当前元素大于等于栈顶元素时才将栈顶元素弹出，然后将当前元素压栈来维护的。这样可以确保栈中的每个元素都是之前遍历过的元素中相对较大的值，便于寻找和栈顶元素构成132模式的其他元素。
在算法中，变量`right`用于记录在当前元素之后（即已经遍历过的部分）的最大值。这个值代表132模式中的‘2’，因为根据132模式的定义，我们需要找到一个比‘2’小的‘1’，以及一个在‘2’之前但比它小的‘3’。当遍历到一个新元素时，如果这个元素小于`right`，则意味着找到了一个可能的‘1’，从而可能形成一个有效的132模式。