0456. 132 Pattern¶
题目信息¶
- 题号:
0456
- 难度:
Medium
- 主题:
三个下标、严格不等式、132 相对大小、存在性判断
- 原题:
- 重点:
必须满足
i < j < k、数值关系为nums[i] < nums[k] < nums[j]、三个值严格不等
题目重述¶
给定整数数组 nums,判断是否存在三个下标 i、j、k,满足 i < j < k,同时满足:
nums[i] < nums[k] < nums[j]
这种下标顺序和数值关系称为 132 模式。nums.length 位于 [1, 2 * 10^5],元素在 32 位有符号整数范围内。三个不等式都是严格的,相等值不能充当其中两个不同层级。
自建示例¶
存在非连续的 132 模式:
输入:nums = [6, 1, 5, 3, 4]
输出:true
解释:选择下标 1、2、3,数值为 1、5、3,满足 1 < 3 < 5。
只有递增关系:
输入:nums = [1, 2, 3, 4]
输出:false
解释:任意较晚元素都不会落在先前较小值和中间较大值之间,无法形成 132 模式。
从右向左维护 3 的候选和最大的 2¶
从右向左扫描时,当前元素可以作为模式中的 1,而右侧需要存在一个 3 和一个介于两者之间的 2。用单调递减栈保存尚未确定为 3 的右侧候选;当当前值大于栈顶时,栈顶可以被当前值确定为 3,并把被弹出的值更新为候选 2。候选 2 取所有已弹出值中的最大值,最容易满足 nums[i] < 2。
若当前值小于候选 2,就已经同时得到 1 < 2 < 3。严格比较保留了题目对三个层级不允许相等的要求。
C++ 实现¶
class Solution {
public:
bool find132pattern(std::vector<int>& nums) {
std::vector<int> stack;
long long middle = LLONG_MIN; // 模式中的 2
for (int i = static_cast<int>(nums.size()) - 1; i >= 0; --i) {
if (static_cast<long long>(nums[i]) < middle) return true;
while (!stack.empty() && nums[i] > stack.back()) {
middle = std::max(middle,
static_cast<long long>(stack.back()));
stack.pop_back();
}
stack.push_back(nums[i]);
}
return false;
}
};
代码分析¶
栈保持递减关系,只有当前值严格大于栈顶时才会弹出并形成“当前值作为 3、栈顶作为 2”的候选;一旦 middle 被设置,后续更左侧元素只需与它比较。每个元素最多入栈、出栈一次,时间复杂度为 O(n),额外空间复杂度为 O(n)。