leetcode334. Increasing Triplet Subsequence

ASCH 发布于2019-08-16 13:47 / 928人阅读

摘要：题目假设有一个无序的数组，如果数组中从左到右存在三个由小到大的数字，则返回。这个思路实在是非常的独特，而且精炼这里它用两个变量分别记录了已经遍历过的数字中最小的数字和第二小的数字，一旦找到比这两个数字都大的数字就证明一定存在一个升序。

题目

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should:

Return true if there exists i, j, k 
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.
Note: Your algorithm should run in O(n) time complexity and O(1) space complexity.

Example 1:

Input: [1,2,3,4,5]
Output: true
Example 2:

Input: [5,4,3,2,1]
Output: false

假设有一个无序的数组，如果数组中从左到右存在三个由小到大的数字，则返回true。否则返回false。

题目的额外要求是：O(n)的时间复杂度和O(1)的空间复杂度

思路一: 找到中间位置

其实我们知道只要找到这样一个数字，该数字左边存在比它小的数字，右边存在比它大的数字，就可以确信该数字一定属于某个上升序列的中间数字。所我们可以先从左往右得出每一个数字左边是否有比它小的数字，再从有望走得出右边是否有比它大的数字，最后再根据这两个信息判断该数字是否为上升序列的中间数字。

    public boolean increasingTriplet(int[] nums) {
        if(nums == null || nums.length < 3) return false;
        
        boolean[] hasLeftMin = new boolean[nums.length];
        boolean[] hasRightMax = new boolean[nums.length];
        
        int left = 0;
        int right = nums.length - 1;
        for(int i = 1 ; i nums[left]) {
                hasLeftMin[i] = true;
            } else {
                left = i;
            }
            if(nums[nums.length - i - 1] < nums[right]) {
                hasRightMax[nums.length - i - 1] = true;
            } else {
                right = nums.length - i - 1;
            }
        }
        
        for(int i = 1 ; i < nums.length - 1 ; i++) {
            if(hasLeftMin[i] && hasRightMax[i]) return true;
        }
        return false;
    }

这种思路虽然遵循了O(N)的时间复杂度，但是违背了O(1）的空间复杂度

思路二：找到最小的两个数字

思路二是从讨论区排名第一的回答中挖过来的。这个思路实在是非常的独特，而且精炼！这里它用两个变量分别记录了已经遍历过的数字中最小的数字和第二小的数字，一旦找到比这两个数字都大的数字就证明一定存在一个升序。

    public boolean increasingTriplet(int[] nums) {
        int small = Integer.MAX_VALUE, big = Integer.MAX_VALUE;
        for(int n : nums) {
            if(n <= small) {
                small = n;
            } else if (n<=big) {
                big = n;
            } else {
                return true;
            }
        }
        return false;
    }

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

私有云云服务器 Triplet Increasing Subsequence Leetcod

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/72332.html

LeetCode 334. Increasing Triplet Subsequence

摘要：描述给定一个未排序的数组，判断这个数组中是否存在长度为的递增子序列。说明要求算法的时间复杂度为，空间复杂度为。示例输入输出示例输入输出思路声明三个变量，，用于表示首先遍历数组，找到第一对满足的数。此时依然有但是，不影响判断的逻辑。 Description Given an unsorted array return whether an increasing subsequence o...

saucxs 2019-07-31 10:14 评论0 收藏0
[Leetcode] Increasing Triplet Subsequence 递增的三元子序列

摘要：如果右面能碰到一个数大于，说明必然存在一个递增的三元组。复杂度空间时间测试代码结果 Given an unsorted array return whether an increasing subsequence oflength 3 exists or not in the array. More specifically, if there exists i , j , k suc...

coordinate35 2019-08-15 14:03 评论0 收藏0
[LeetCode] Increasing Triplet Subsequence

摘要：题目不要求连续的三个增长数，所以只需要更新其中较小的两个数，并在第三个数满足条件的情况下返回即可。 Problem Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array. Formally the function should:Re...

cooxer 2019-08-14 14:03 评论0 收藏0
LeetCode 攻略 - 2019 年 8 月上半月汇总（109 题攻略）

摘要：每天会折腾一道及以上题目，并将其解题思路记录成文章，发布到和微信公众号上。三汇总返回目录在月日月日这半个月中，做了汇总了数组知识点。或者拉到本文最下面，添加的微信等会根据题解以及留言内容，进行补充，并添加上提供题解的小伙伴的昵称和地址。 LeetCode 汇总 - 2019/08/15 Create by jsliang on 2019-08-12 19:39:34 Recently...

tracy 2019-08-26 10:49 评论0 收藏0
LeetCode[300] Longest Increasing Subsequence

摘要：再用二分法找当前值应该在排好序的数组中的插入位置。因为要找的是最长的序列，所以每次将排好序的数组中替换成已经排好序的，会能保证得到的结果是最长的。保证升序相等也要替换这个值 LeetCode[300] Longest Increasing Subsequence Given an unsorted array of integers, find the length of longe...

blankyao 2019-08-14 15:01 评论0 收藏0