0334. Increasing Triplet Subsequence (M)

佚名 4年前 (2020-06-30) 算法 759人围观抢沙发百度已收录

Increasing Triplet Subsequence (M)

题目

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

Formally the function should:

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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

题意

判断给定数组中是否存在一组下标为i、j、k的数，满足i<j<k且arr[i]<arr[j]<arr[k]。要求时间复杂度为\(O(N)\)且空间复杂度为\(O(1)\)。

思路

如果没有空间复杂度的要求，比较容易想到的方法是再建两个数组leftMax和rightMin，leftMax[i]表示从首元素到i中最大的数，rightMin[j]表示从j到末元素中最小的数，如果存在leftMax[i]<arr[i]<rightMin[i]，说明存在满足条件的三元组。

为了满足\(O(1)\)的空间复杂度要求，可以这样实现：设两个变量small和mid，从左向右遍历数组，如果arr[i]<=small，更新small，否则如果arr[i]<=mid，更新mid，这样当遍历到下标为i的数时，small表示0-(i-1)中最小的数，mid表示0-(i-1)中第二小的数 (描述的是存在关系，具体的相对位置不一定正确)，只要arr[i]>mid，说明就能构成严格递增的三元组。

代码实现

Java

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