增加三元组子序列

Question

我正在 leetcode.com 上尝试增加三元组子序列问题

我一开始采用了蛮力方法，但遇到了超时问题，但通过了几乎所有测试用例。代码如下：

public static void main(String[] args) {
        IncreasingTriplet it = new IncreasingTriplet();
        int[] nums = { 1, 5, 0, 4, 1, 3 };
        System.out.println(it.increasingTriplet(nums));
    }

    public boolean increasingTriplet(int[] nums) {
        // if there are less than 3 numbers return false;
        if (nums.length < 3)
            return false;
        return helper(nums, nums.length, Integer.MIN_VALUE, 0, 0);
    }

    private boolean helper(int[] nums, int n, int prev, int index, int count) {
        if (index >= n) {
            if (count < 3) {
                return false;
            } else if (count == 3) {
                return true;
            }
            return false;
        } else if (count == 3) {
            return true;
        } else if (count > 3) {
            return false;
        }
        if (nums[index] > prev) {
            if (helper(nums, n, nums[index], index + 1, count + 1) || helper(nums, n, prev, index + 1, count)) {
                return true;
            }
            return false;
        }
        return helper(nums, n, prev, index + 1, count);

然后我看到了一个模式，并决定将所讨论的“索引”是否是递增三元组序列的一部分的结果存储为序列中的第一个、第二个或第三个数字。 这意味着我需要创建一个缓存来跟踪 0, 1,2 位置中的每个索引cache[][] = new int[nums.length][3]。 我没有通过所有测试用例。任何人都可以提供一些指导来说明这种方法是否错误？任何建议都表示赞赏。

带有缓存的代码如下：

public boolean increasingTriplet(int[] nums) {
        //if there are less than 3 numbers return false;
        if(nums.length < 3) return false;
        int[][]cache = new int[nums.length][4];
        for(int i = 0; i < cache.length; i++){
            for(int j = 0; j < cache[0].length; j++){
                cache[i][j] = -1;
            }
        }
        return helper(nums, nums.length, Integer.MIN_VALUE, 0, 0, cache);
    }
    //Let's optimize by keeping track of the index as either part of the sequence as 1st, 2nd or 3rd and then store that for future use.
    private boolean helper(int[] nums, int n, int prev, int index, int count, int[][]cache){
        if(index >= n){
            if(count < 3){
                return false;
            }
            if( count == 3){
                return true;
            }
            return false;
        }
        if(count == 3){
            return true;
        }
        if(count > 3){
            return false;
        }
        if(cache[index][count] != -1){
            return cache[index][count] == 1? true:false;
        }
        if(nums[index] > prev){
            if(helper(nums, n, nums[index], index + 1, count + 1, cache) || helper(nums, n, prev, index + 1, count, cache)){
                cache[index][count] = 1;
                return true;
            }
            cache[index][count] = 0;
            return false;
        }
        return helper(nums, n, prev, index + 1, count, cache);
    }

Answer 1

你不需要动态规划。相反，您可以将每个索引检查为可能的中间索引，即数组中其左侧的值小于该索引的值，数组中索引右侧的值大于该索引的值。

这些都可以通过在向前迭代时跟踪迄今为止的最小值，然后在向后迭代时保持最大值来在线性时间内预先计算。

public boolean increasingTriplet(int[] nums) {
    var hasLess = new boolean[nums.length];
    int min = Integer.MAX_VALUE;
    for (int i = 0; i < nums.length; ++i) {
        hasLess[i] = min < nums[i];
        min = Math.min(min, nums[i]);
    }
    int max = Integer.MIN_VALUE;
    for (int i = nums.length - 1; i >= 0; i--) {
        if (hasLess[i] && max > nums[i]) return true;
        max = Math.max(max, nums[i]);
    }
    return false;
}

请注意，这也可以通过 O(1) 额外空间来解决。

Answer 2

这是一个Python 快速解决方案。翻译应该很容易。

def has_increasing_triplet (array):
    too_big = max(array) + 1
    first = second = third = too_big
    for v in array:
        if v <= first:
            first = v
        elif v <= second:
            second = v
        elif v < third:
            return True
    return False

逻辑很简单。

first

是迄今为止遇到的最小的东西。

second

是遇到时比

first

大的最小的东西。所以是两个的递增序列。如果我们尝试设置

third

，我们就会发现递增的三元组。

这是

O(1)

记忆和

O(n)

工作。