LeetCode_贪心算法_中等_334. 递增的三元子序列

梦里梦外; 2023-10-06 23:12 6阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

**给你一个整数数组 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) 的解决方案吗？

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/increasing-triplet-subsequence

## 2.思路 ##

（1）暴力穷举法  
暴力穷举法比较容易想到，使用三层 for 循环遍历所有可能的三元组下标 (i, j, k) ，并逐个进行判断即可。但显然该方法的时间复杂度较高，在 LeetCode 中提交时会显示“超出时间限制”的提示！

（2）贪心算法  
思路参考[本题官方题解][Link 1]。

## 3.代码实现（Java） ##

//思路1————暴力穷举法
    class Solution {
        
        public boolean increasingTriplet(int[] nums) {
        
            boolean flag = false;
            int length = nums.length;
            for (int i = 0; i < length - 2; i++) {
        
                for (int j = i + 1; j < length - 1; j++) {
        
                    if (nums[i] < nums[j]) {
        
                        for (int k = j + 1; k < length; k++) {
        
                            if (nums[j] < nums[k]) {
        
                                return true;
                            }
                        }
                    }
                }
            }
            return flag;
        }
    }

//思路2————贪心算法
    class Solution {
        
    	public boolean increasingTriplet(int[] nums) {
        
    		/*
    			本题贪心算法的主要思想：
    			为了找到递增的三元子序列，first 和 second 应该尽可能地小，此时找到递增的三元子序列的可能性更大					
    		*/
            int length = nums.length;
            int first = nums[0];
            int second = Integer.MAX_VALUE;
            //下面在遍历的过程中，始终保证 first < second
            for (int i = 1; i < length; i++) {
        
            	//遍历到的每一个 num 可以看作要找的第 3 个数
                int num = nums[i];
                if (num > second) {
        
                	// first < second < num，找到了符合条件的三元组，直接返回 true
                    return true;
                } else if (num > first) {
        
                	// first < num <= second，将 num 赋值给 second，尽可能保证 first 和 second 之间的差距较小，以便于寻找第 3 个数
                    second = num;
                } else {
        
                	// num <= first < second，将 first 更新为 num
                    first = num;
                }
            }
            return false;
        }
    }

[Link 1]: https://leetcode.cn/problems/increasing-triplet-subsequence/solution/di-zeng-de-san-yuan-zi-xu-lie-by-leetcod-dp2r/