[LeetCode] Increasing Triplet Subsequence

cooxer 发布于2019-08-14 14:03 / 3032人阅读

摘要：题目不要求连续的三个增长数，所以只需要更新其中较小的两个数，并在第三个数满足条件的情况下返回即可。

Problem

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.
Your algorithm should run in O(n) time complexity and O(1) space complexity.

Examples

Given [1, 2, 3, 4, 5],
return true.

Given [5, 4, 3, 2, 1],
return false.

Note

题目不要求连续的三个增长数，所以只需要更新其中较小的两个数，并在第三个数满足条件的情况下返回true即可。
怎么更新较小的两个数呢，先判断新数是否最小的数，如果是便更新，如果不是，再判断是否第二小的数，如果是便更新，如果不是，那么一定是最大的数，则符合题意，返回TRUE。

Solution

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

服务器托管云服务器 Triplet Increasing Subsequence LeetCode

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

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

[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 334. Increasing Triplet Subsequence

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

saucxs 2019-07-31 10:14 评论0 收藏0
leetcode334. Increasing Triplet Subsequence

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

ASCH 2019-08-16 13:47 评论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
[LeetCode] 300. Longest Increasing Subsequence

Problem Given an unsorted array of integers, find the length of longest increasing subsequence. Example: Input: [10,9,2,5,3,7,101,18]Output: 4 Explanation: The longest increasing subsequence is [2,3,7...

luckyyulin 2019-08-19 11:13 评论0 收藏0