0334. Increasing Triplet Subsequence
====================================
题目信息
--------
:题号: 0334
:难度: Medium
:主题: 数组、三元素子序列、严格递增、下标顺序
:原题: `LeetCode 0334 `_
:重点: 三个下标必须严格递增、三个数值也必须严格递增、元素不要求连续
题目重述
--------
给定整数数组 ``nums``,判断是否存在三个下标 ``i``、``j``、``k``,满足 ``i < j < k`` 且 ``nums[i] < nums[j] < nums[k]``。只要存在任意一组三元素严格递增子序列就返回 ``true``,否则返回 ``false``。
数组长度位于 ``[1, 5 * 10^5]``,元素位于 32 位有符号整数范围。三个元素在原数组中可以不连续,但不能改变出现顺序;相等值不能满足严格递增条件。进阶要求 ``O(n)`` 时间和 ``O(1)`` 额外空间。
自建示例
--------
需要跳过中间元素:
.. code-block:: text
输入:nums = [5, 1, 4, 2, 3]
输出:true
解释:下标 1、3、4 对应的数值 1、2、3 严格递增,虽然它们不是从数组开头连续取得。
只有相等值:
.. code-block:: text
输入:nums = [3, 3, 3]
输出:false
解释:任意三个值都相等,不满足严格小于关系。
只保留最有希望的前两个数
--------------------------
扫描到当前位置时,维护一个最小的 ``first``,以及在 ``first`` 之后出现、且尽可能小的 ``second``。遇到 ``x``:若 ``x <= first``,用它替换 ``first``;否则若 ``x <= second``,用它替换 ``second``;若 ``x`` 同时大于两者,就得到 ``first < second < x`` 的三元组。
替换不会破坏下标顺序:``first`` 只来自当前或更早位置,``second`` 只在当前值大于 ``first`` 时更新,因此保存的 ``first`` 必定位于 ``second`` 之前。用 ``<=`` 更新是为了让相等值不能错误地推进到更长的严格序列,同时给后续更大值留下最小前缀。
C++ 实现
--------
.. code-block:: cpp
class Solution {
public:
bool increasingTriplet(std::vector& nums) {
int first = INT_MAX;
int second = INT_MAX;
for (int value : nums) {
if (value <= first) {
first = value;
} else if (value <= second) {
second = value;
} else {
return true;
}
}
return false;
}
};
代码分析
--------
``first`` 和 ``second`` 不是固定的某两个下标,而是到当前位置为止最有利于扩展的状态;较小的前缀不会减少后续可选值。两个变量始终保持严格候选关系,第三次进入 ``else`` 才返回真。算法只扫描一次数组,时间复杂度为 ``O(n)``,额外空间为 ``O(1)``。