Leetcode 334. 递增的三元子序列

题目

给定一个未排序的数组，判断这个数组中是否存在长度为 3 的递增子序列。

数学表达式如下:

如果存在这样的 i, j, k, 且满足 0 ≤ i < j < k ≤ n-1， 使得 arr[i] < arr[j] < arr[k] ，返回 true ; 否则返回 false 。 说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1) 。

测试样例

示例 1:

输入: [1,2,3,4,5] 输出: true

示例 2:

输入: [5,4,3,2,1] 输出: false

题解

我们用一个变量small记录最小的数，用一个变量mid记录比small大的数。显然，当给mid赋值的时候，说明存在i<j，使得nums[i]<nums[j]，这时候，我们只要找到一个比mid大的数，就说明我们找到了递增的三元子序列了。详细过程见代码

代码

bool increasingTriplet(vector<int>& nums) { if(nums.size() < 2) return false; int n =nums.size(); int small = INT_MAX,mid = INT_MAX; for(int i=0; i<n; i++){ if(nums[i]<=small){ small = nums[i]; }else if(nums[i]<=mid){ //进入这个if语句，一定存在i<j,使得nums[i]<nums[j] mid = nums[i]; } if(nums[i] > mid) return true; } return false; }

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/increasing-triplet-subsequence 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。