[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

二、题目分析和代码实现

1、第一种方法——最直接的思路

1）采用动态规划的方法，dp[i]代表以nums[i]为结尾的递增子序列长度
2）dp[i]=max{dp[j]+1},j<i&&nums[j]<nums[i]
3）时间复杂度为n*n

 class Solution {

 public:

     bool increasingTriplet(vector<int>& nums) {

         int n = nums.size();

         if (n < )return false;

         vector<int>dp(n, );

         for (int i = ; i < n; ++i) {

             for (int j = ; j < i; ++j) {

                 if (nums[j] < nums[i])

                     dp[i] = max(dp[i], dp[j] + );

             }

             if (dp[i] == )return true;

         }

         return false;

     }

 };

2、符合题目要求的方法——最佳思路，但是比较难想

1）用两个数字m1代表当前最小的数，m2代表遍历到现在第二小的数，m2的位置不一定要在m1之后
2）那么当发现一个数大于m2的数的时候，就直接返回true
3）时间复杂度为n,空间复杂度为常数

 class Solution {

 public:

     bool increasingTriplet(vector<int>& nums) {

         int n = nums.size();

         int m1 = INT_MAX, m2 = INT_MAX;

         for (int i = ; i < n; ++i) {

             if (nums[i] <= m1)m1 = nums[i];

             else if (nums[i] <= m2)m2 = nums[i];//要注意等号，也就是遇到相等的也要向后移动

             else return true;

         }

         return false;

     }

 };

3）另一种方法——思路很赞

1）Min[i]代表从0到i的最小值，Max[i]代表从i到n的最大值
2）如果nums[i]大于Min[i-1]并且小于Max[i+1]，那么就返回真
3）时间复杂度为n,空间复杂度为n

 class Solution {

 public:

     bool increasingTriplet(vector<int>& nums) {

         int n = nums.size();

         if (n < )return false;

         vector<int> Min(n), Max(n);

         int i;

         Min[] = nums[], Max[n - ] = nums[n - ];

         for (i = ; i < n; ++i) {

             Min[i] = min(Min[i - ], nums[i]);

             Max[n -  - i] = max(Max[n - i], nums[n -  - i]);//注意下标

         }

         for (int i = ; i < n - ; ++i) {

             if (nums[i] > Min[i - ] && nums[i] < Max[i + ])

                 return true;

         }

         return false;

     }

 };

巴特西

[Leetcode] 第334题递增的三元子序列

最新文章

热门文章

巴特西

[Leetcode] 第334题 递增的三元子序列

最新文章

热门文章

[Leetcode] 第334题递增的三元子序列