334.递增的三元子序列

334.递增的三元子序列

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

如果存在这样的三元组下标 ( i , j , k ) (i, j, k) (i,j,k)且满足 i < j < k i < j < k i 样例

考虑比较容易想到的做法：

假如数组大小小于3，直接返回 f a l s e false false。

每次考虑将数字 n u m s [ i ] nums[i] nums[i]作为三元序列的中间数，那么就需要考虑数组 [ 0 , i − 1 ] [0,i-1] [0,i−1]是否存在一个数字小于 n u m s [ i ] nums[i] nums[i]，这个很容易做到：在顺序遍历数组的时候维护一个minn表示 [ 0 , i − 1 ] [0,i-1] [0,i−1]之前的最小数。然后还需要考虑数组 [ i + 1 , n − 1 ] ( n = 数 组 大 小 ) [i+1,n-1](n= 数组大小) [i+1,n−1](n=数组大小)之前存在一个数字大于nums[i]，这个就没办法像刚才维护minn一样维护maxx，并且是从0到n-1进行遍历，意味着维护的数字的数量在不断减少，意味着最大值也可能发生不同的变化。考虑简单的做法：维护一个multiset，在遍历的时候每次弹出一个等于 n u m s [ i ] nums[i] nums[i]的数字，相当于 n u m s [ i ] nums[i] nums[i]从multiset中删除（因为一开始multiset是加入了数组 [ 1 , n − 1 ] [1,n-1] [1,n−1]的所有数字），然后二分查找是否存在一个数字大于 n u m s [ i ] nums[i] nums[i]，如果不存在，返回的迭代器就是multiset.end()。这样就可以通过维护minn和multiset来寻找一个三元子序列。（时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)）

class Solution {
public:
    bool increasingTriplet(vector& nums) {
        int n=nums.size();
        if(n<3)return 0;
        multisets1,s2;
        for(int i=n-1;i>=1;i--)s2.insert(nums[i]);
        int minn=nums[0];
        for(int i=1;i 
思路2 
使用贪心的方法将空间复杂度降到
    
     
      
       
        O
       
       
        (
       
       
        1
       
       
        )
       
      
      
       O(1)
      
     
    O(1)。从左到右遍历数组
    
     
      
       
        n
       
       
        u
       
       
        m
       
       
        s
       
      
      
       nums
      
     
    nums，维护两个变量minn1和minn2，分别作为三元子序列的第一个数字和第二个数字，并且保证
    
     
      
       
        f
       
       
        i
       
       
        r
       
       
        s
       
       
        t
       
       
        <
       
       
        s
       
       
        e
       
       
        c
       
       
        o
       
       
        n
       
       
        d
       
      
      
       first 
初始：
    
     
      
       
        f
       
       
        i
       
       
        r
       
       
        s
       
       
        t
       
       
        =
       
       
        n
       
       
        u
       
       
        m
       
       
        s
       
       
        [
       
       
        0
       
       
        ]
       
       
        ，
       
       
        s
       
       
        e
       
       
        c
       
       
        o
       
       
        n
       
       
        d
       
       
        =
       
       
        i
       
       
        n
       
       
        f
       
      
      
       first=nums[0]，second=inf
      
     
    first=nums[0]，second=inf。
 
当遍历到
    
     
      
       
        n
       
       
        u
       
       
        m
       
       
        s
       
       
        [
       
       
        i
       
       
        ]
       
      
      
       nums[i]
      
     
    nums[i]时，有如下操作：
 
如果
     
      
       
        
         n
        
        
         u
        
        
         m
        
        
         s
        
        
         [
        
        
         i
        
        
         ]
        
        
         >
        
        
         s
        
        
         e
        
        
         c
        
        
         o
        
        
         n
        
        
         d
        
       
       
        nums[i]>second
       
      
     nums[i]>second，说明找到了一个递增的三元子序列，返回
     
      
       
        
         t
        
        
         r
        
        
         u
        
        
         e
        
       
       
        true
       
      
     true;如果
     
      
       
        
         n
        
        
         u
        
        
         m
        
        
         s
        
        
         [
        
        
         i
        
        
         ]
        
        
         <
        
        
         =
        
        
         s
        
        
         e
        
        
         c
        
        
         o
        
        
         n
        
        
         d
        
        
         ，
        
        
         n
        
        
         u
        
        
         m
        
        
         s
        
        
         [
        
        
         i
        
        
         ]
        
        
         >
        
        
         f
        
        
         i
        
        
         r
        
        
         s
        
        
         t
        
       
       
        nums[i]<=second ，nums[i]>first
       
      
     nums[i]<=second，nums[i]>first ，那么更新
     
      
       
        
         s
        
        
         e
        
        
         c
        
        
         o
        
        
         n
        
        
         d
        
        
         =
        
        
         n
        
        
         u
        
        
         m
        
        
         s
        
        
         [
        
        
         i
        
        
         ]
        
       
       
        second=nums[i]
       
      
     second=nums[i]；否则更新
     
      
       
        
         f
        
        
         i
        
        
         r
        
        
         s
        
        
         t
        
        
         =
        
        
         n
        
        
         u
        
        
         m
        
        
         s
        
        
         [
        
        
         i
        
        
         ]
        
       
       
        first=nums[i]
       
      
     first=nums[i]; 
如果遍历结束时没有找到递增的三元子序列，返回
    
     
      
       
        f
       
       
        a
       
       
        l
       
       
        s
       
       
        e
       
      
      
       false
      
     
    false。
 
需要递增的三元子序列的过程要求：
    
     
      
       
        f
       
       
        i
       
       
        r
       
       
        s
       
       
        t
       
      
      
       first
      
     
    first和
    
     
      
       
        s
       
       
        e
       
       
        c
       
       
        o
       
       
        n
       
       
        d
       
      
      
       second
      
     
    second应该尽可能地小，这样找到递增的三元子序列的可能性更大。
 
要求
    
     
      
       
        f
       
       
        i
       
       
        r
       
       
        s
       
       
        t
       
       
        <
       
       
        s
       
       
        e
       
       
        c
       
       
        o
       
       
        n
       
       
        d
       
      
      
       first
       
       
        s
       
       
        e
       
       
        c
       
       
        o
       
       
        n
       
       
        d
       
      
      
       nums[i]>second
      
     
    nums[i]>second，此时first一定出现在second前面，所以
    
     
      
       
        (
       
       
        f
       
       
        i
       
       
        r
       
       
        s
       
       
        t
       
       
        ,
       
       
        s
       
       
        e
       
       
        c
       
       
        o
       
       
        n
       
       
        d
       
       
        ,
       
       
        n
       
       
        u
       
       
        m
       
       
        s
       
       
        [
       
       
        i
       
       
        ]
       
       
        )
       
      
      
       (first,second,nums[i])
      
     
    (first,second,nums[i])一定是递增的三元子序列。
 
考虑一个比较问题：如果遍历过程中遇到小于
     
      
       
        
         f
        
        
         i
        
        
         r
        
        
         s
        
        
         t
        
       
       
        first
       
      
     first的元素，则会用该元素更新
     
      
       
        
         f
        
        
         i
        
        
         r
        
        
         s
        
        
         t
        
       
       
        first
       
      
     first，这导致了first顺序在second之后，是否会出现误判？
 
不会。虽然更新后的
    
     
      
       
        f
       
       
        i
       
       
        r
       
       
        s
       
       
        t
       
      
      
       first
      
     
    first出现在
    
     
      
       
        s
       
       
        e
       
       
        c
       
       
        o
       
       
        n
       
       
        d
       
      
      
       second
      
     
    second的后面，但是second之前必然有一个比second小的数字
    
     
      
       
        f
       
       
        i
       
       
        r
       
       
        s
       
       
        
         t
        
        
         ′
        
       
      
      
       first'
      
     
    first′，如果突然遇到了
    
     
      
       
        n
       
       
        u
       
       
        m
       
       
        s
       
       
        [
       
       
        i
       
       
        ]
       
       
        >
       
       
        s
       
       
        e
       
       
        c
       
       
        o
       
       
        n
       
       
        d
       
      
      
       nums[i]>second
      
     
    nums[i]>second，那么一定有递增三元序列
    
     
      
       
        (
       
       
        f
       
       
        i
       
       
        r
       
       
        s
       
       
        
         t
        
        
         ′
        
       
       
        ,
       
       
        s
       
       
        e
       
       
        c
       
       
        o
       
       
        n
       
       
        d
       
       
        ,
       
       
        n
       
       
        u
       
       
        m
       
       
        s
       
       
        [
       
       
        i
       
       
        ]
       
       
        )
       
      
      
       (first',second,nums[i])
      
     
    (first′,second,nums[i])。
 
代码2 
class Solution {
public:
    bool increasingTriplet(vector& nums) {
        int minn1=nums[0],minn2=(1ll<<31)-1;
        for(int i=1;iminn2)return 1;
            else if(nums[i]>minn1)minn2=nums[i];
            else minn1=nums[i];
        }
        return 0;
    }
};