算法每日一练（2022年1月12日）

算法每日一练（2022年1月12日） 2022年1月12日 递增的三元子序列 题目描述

给你一个整数数组 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 <= 5 * 105-231 <= nums[i] <= 231 - 1

**进阶：**你能实现时间复杂度为 O(n) ，空间复杂度为 O(1) 的解决方案吗？

题解 贪心

可以使用贪心的方法将空间复杂度降到 O(1)。从左到右遍历数组 nums，遍历过程中维护两个变量 first 和 second，分别表示递增的三元子序列中的第一个数和第二个数，任何时候都有 first

初始时，first=nums[0]，second=+∞。对于 1≤i

如果 num>second，则找到了一个递增的三元子序列，返回 true；

否则，如果 num>first，则将 second 的值更新为 num；

否则，将 first 的值更新为 num。

如果遍历结束时没有找到递增的三元子序列，返回 false。

上述做法的贪心思想是：为了找到递增的三元子序列，first 和 second 应该尽可能地小，此时找到递增的三元子序列的可能性更大。

假设 (first,second,num) 是一个递增的三元子序列，如果存在 second’ 满足 first

同理可得，三元子序列的第一个数也应该尽可能地小。

如果遍历过程中遇到的所有元素都大于 first，则当遇到 num>second 时，first 一定出现在 second 的前面，second 一定出现在 num 的前面，(first,second,num) 即为递增的三元子序列。

如果遍历过程中遇到小于 first 的元素，则会用该元素更新 first，虽然更新后的 first 出现在second 的后面，但是在 second 的前面一定存在一个元素 first’ 小于 second，因此当遇到 num>second 时，(first’,second,num) 即为递增的三元子序列。

根据上述分析可知，当遇到 num>second 时，一定存在一个递增的三元子序列，该三元子序列的第二个数和第三个数分别是 second 和 num，因此返回 true。

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/increasing-triplet-subsequence/solution/di-zeng-de-san-yuan-zi-xu-lie-by-leetcod-dp2r/
来源：力扣（LeetCode）

num有三种情况：

num>second：满足三元递增序列，返回truefirst 代码实现

//我的解题过程
package everyday_answer_day5;

public class Solution {
    public boolean increasingTriplet(int[] nums) {
    	//首先长度小于3，不满足3元
    	if (nums.length<3) {
			return false;
		}
    	int first=nums[0];
    	int second=Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
			int num=nums[i];
			if (num>second) {
				return true;
			}else if(num>first) {
				second=num;
			}else {
				first=num;
			}
		}
    	
    	return false;
    }
}

//时间复杂度o(n），n是nums数组的长度，需要遍历数组一次
//空间复杂度o(1)

//官方题解
class Solution {
    public boolean increasingTriplet(int[] nums) {
        int n = nums.length;
        if (n < 3) {
            return false;
        }
        int first = nums[0], second = Integer.MAX_VALUE;
        for (int i = 1; i < n; i++) {
            int num = nums[i];
            if (num > second) {
                return true;
            } else if (num > first) {
                second = num;
            } else {
                first = num;
            }
        }
        return false;
    }
}

复杂度分析

时间复杂度o(n），n是nums数组的长度，需要遍历数组一次空间复杂度o(1) 我的看法

今天题目很短，看起来也不难，但是自己还是没有思路，可能是自己练的少，自己看了看别人的视频讲解，自己也能够理解，但是自己就是没有思路。

这道题方法就是利用贪心算法，先找到局部的最优解，在通过局部最优解找到全局的最优解。

加油，每天进步一点点！

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/zaji/5702784.html