LeetCode-08-三元递增子序列

发表于 更新于 阅读次数： 本文字数： 658 阅读时长 ≈ 2 分钟

LeetCode算法题：元素之积。

题目

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

如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。

提示：

  • 1 <= nums.length <= 5 * 105
  • -231 <= nums[i] <= 231 - 1

思路

首先区分题干要求，递增三元子序列。由原序列中任意n个元素可组成一个n元子序列，例如：

1
a = [1,2,4,6,7,8]

其中[1,2,4]、[1,4,7]均为a的子序列，如果有顺序要求，则判断条件更广。

因此，最基础的思路是使用三重循环遍历，直至找到，或者遍历完成。

代码

###　方案Ａ-遍历

以首元素为i的起点，次元素为j起点，第三个元素为k的起点。但是改方案嵌套三重循环，不适用数据量较大的情况。

       <!--块级封装-->
<center>    <!--将图片和文字居中-->
<img src="2025-08-09-LeetCode-08-Increasing_Triplet/A.jpg"
     alt="image can't load."
     style="zoom:100%"/><!-- alt内为提示词-->
三循环，时间O(n^3)<!--标题-->
</center>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
bool increasingTriplet(int* nums, int numsSize) {
    bool result = false;
    if(numsSize < 3)
    {
        return result;
    }

    for(int i=0; i<numsSize-2; i++)
    {
        for(int j=i+1; j<numsSize - 1; j++)
        {
            for(int k=j+1; k<numsSize; k++)
            {
                if(nums[i]<nums[j] && nums[j]<nums[k])
                {
                    return true;
                }
            }
        }
    }

    return result;
}

方案B-贪心

方案A的时间复杂度较大，换种思路，即三个元素相互对比，其大小关系只有以下几种：

  • i < j < k，单调递增
  • i < j，i < k < j，新数组在前方两个数据之间
  • k < i < j，新数据最小

因此定义min存储整个序列的最小值，second存储的数据不定，但一定保证前方存在一个数据<second。

       <!--块级封装-->
<center>    <!--将图片和文字居中-->
<img src="2025-08-09-LeetCode-08-Increasing_Triplet/B.jpg"
     alt="image can't load."
     style="zoom:100%"/><!-- alt内为提示词-->
贪心，时间O(n)空间O(1)<!--标题-->
</center>

如上图，尽管最后的结果使用的是mid2、min3和末尾值，但在mid2之前一定有一个更小的min1（否则mid为初值INT_MAX，不可能有比其更大的值）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
bool increasingTriplet(int* nums, int numsSize) {
    if(numsSize < 3) 
        return false;
    bool result = false;
    int min = nums[0];
    int mid = INT_MIX; // 初始化为最大值
    
    for(int i=0; i<numsSize; i++)
    {
     	// 三元素递增
        if(mid < nums[i]) 
        {
            result = true;
            break;
        }
        // 刷新次最小的元素值，前方一定有比他更小的
        else if(min < nums[i])
        {
            mid = nums[i];
        }
        else
        {
            min = nums[i];
        }
    }
    return result;
}

————————— End —————————

白日放歌须纵酒，青春作伴好还乡。–《闻官军收河南河北》