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