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)``。