leetcode 334. Increasing Triplet Subsequence | 334. 递增的三元子序列（一种较trick的解法）

快来打我* 2023-01-23 13:52 2阅读 0赞

## 题目 ##

[https://leetcode.com/problems/increasing-triplet-subsequence/][https_leetcode.com_problems_increasing-triplet-subsequence]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]

## 题解 ##

看到这题，首先，没有思路…

然后，看了下面的 Related Questions，找到了之前看答案写的 [300. Longest Increasing Subsequence][] \[[题解][Link 1]\]，用这个思路，写了一个 dp，O(n^2) 的时间复杂度，结果超时了。

原来的办法不可行，所以还是没有思路，于是看了[答案][Link 2]。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]

##### 如何理解上述 “有一个比 small 大比 mid 小的前最小值出现在 mid 之前”？ #####

看图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 2]

上代码：

class Solution { 
        public boolean increasingTriplet(int[] nums) { 
            int a = Integer.MAX_VALUE;
            int b = Integer.MAX_VALUE;
            for (int num : nums) { 
                if (num <= a) a = num;
                else if (num <= b) b = num;
                else return true;
            }
            return false;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 3]

[https_leetcode.com_problems_increasing-triplet-subsequence]: https://leetcode.com/problems/increasing-triplet-subsequence/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20221004/0d080f7b55fc4f83951ac9b27afcd919.png
[300. Longest Increasing Subsequence]: https://leetcode.com/problems/longest-increasing-subsequence/
[Link 1]: https://hanquan.blog.csdn.net/article/details/118487526
[Link 2]: https://leetcode-cn.com/problems/increasing-triplet-subsequence/solution/c-xian-xing-shi-jian-fu-za-du-xiang-xi-jie-xi-da-b/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]: /images/20221004/e31048c204c14c26939b15ecfa459b67.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 2]: /images/20221004/9ed90a6f42644dbcabab74b98fe3a680.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 3]: /images/20221004/cc8729f6f88e4fd7952649a3f25d142f.png