AlgoPressAppearance
0334-递增的三元子序列
https://leetcode.cn/problems/increasing-triplet-subsequence
给你一个整数数组nums ，判断这个数组中是否存在长度为 3 的递增子序列。 如果存在这样的三元组下标 (i, j, k)且满足 i < j < k ，使得nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。
示例 1：
输入：nums = [1,2,3,4,5]
输出：true
解释：任何 i < j < k 的三元组都满足题意
示例 2：
输入：nums = [5,4,3,2,1]
输出：false
解释：不存在满足题意的三元组
示例 3：
输入：nums = [2,1,5,0,4,6]
输出：true
解释：三元组 (3, 4, 5) 满足题意，因为 nums[3] == 0 < nums[4] == 4 < nums[5] == 6
提示：
1 <= nums.length <= 10^5
-2^31 <= nums[i] <= 2^31 - 1
进阶：你能实现时间复杂度为 O(n) ，空间复杂度为 O(1) 的解决方案吗？
思路1：动态规划【思路正确，会超时】
动态规划, dp[i] 表示递增当前位置递增子序列的最大长度,初始为1, 如果 nums[i] > nums[j] dp[i] = max(dp[j])+1, 其中 0<j<i 最后判断是否大于 3
参考代码
csharp
public class Solution {
public bool IncreasingTriplet(int[] nums) {
int n = nums.Length;
if(n < 3){
return false;
}
int[] dp = new int[n];
//初始化为1，因为至少可以作为一个递增子序列
for(int i=0; i<dp.Length; i++){
dp[i] = 1;
}
//状态转移
int max = 1;
for(int i=1;i<n;i++){
for(int j=0;j<i;j++){
if(nums[i] > nums[j]){
dp[i] = Math.Max(dp[i],dp[j]+1);
max = Math.Max(dp[i],max);
}
}
}
return max >= 3;
}
}
思路2：进阶【官方】
时间复杂度为 O(n) ，空间复杂度为 O(1) 的解决方案 思路 Tricky https://leetcode.cn/problems/increasing-triplet-subsequence/solution/c-xian-xing-shi-jian-fu-za-du-xiang-xi-jie-xi-da-b/
参考代码
csharp
public class Solution {
public bool IncreasingTriplet(int[] nums) {
int n = nums.Length;
if(n < 3){
return false;
}
int min = int.MaxValue;
int mid = int.MaxValue;
for(int i=0; i<n; i++){
if(nums[i] <= min){
min = nums[i];
}
else if(nums[i] <= mid){
mid = nums[i];
}
else if(nums[i] > mid){
return true;
}
}
return false;
}
}
复习：20220622
csharp
public class Solution {
public bool IncreasingTriplet(int[] nums) {
int min = int.MaxValue;
int mid = int.MaxValue;
for(int i=0; i<nums.Length; i++){
if(nums[i] < min){ //优先找最小的数
min = nums[i];
}
else if(nums[i] > min){ //取mid值
mid = Math.Min(nums[i],mid);
}
if(nums[i] > mid){ //当大于mid时成立，即便上一步重新设置过 min 但是不影响 之前右min再mid前面，因为mid是在min之后才会赋值的
return true;
}
}
return false;
}
}