文章 224
评论 6
浏览 200772
Array - 334. Increasing Triplet Subsequence

Array - 334. Increasing Triplet Subsequence

334. Increasing Triplet Subsequence

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

思路:

这道题可以用动态规划来做,记录每一位为止的最长子序列的长度。时间复杂度和空间复杂度都是O(n), 当然也可以把空间复杂度优化成O(1),也就是只记录两位。但是这题我选择greedy来做。

代码:

class Solution {

    public boolean increasingTriplet(int[] nums) {
        if (nums == null || nums.length <= 2) return false;
        
        int min1 = Integer.MAX_VALUE;
        int min2 = Integer.MAX_VALUE;
        
        for (int num : nums) {
            if (num > min2) {
                return true;
            } else if (num < min1) {
                min1 = num;
            } else if (num > min1 && num < min2) {
                min2 = num;
            }
        }
        
        return false;
    }
}

标题:Array - 334. Increasing Triplet Subsequence
作者:michael
地址:https://www.bitbo-liuyang.com/articles/2019/06/16/1560694416032.html

Nothing just happens, it's all part of a plan.

取消