Leetcode 334. Increasing Triplet Subsequence

[Woodyiiiiiii]

这道题要求O(n)时间复杂度，O(1)空间复杂度。

首先不管空间复杂度，先看时间复杂度。首先想到贪心的方法；其次注意是三元组，所以可以通过两次遍历，分别是从左到右、从右到左来实现标记。

class Solution {
    public boolean increasingTriplet(int[] nums) {
        int n = nums.length;
        if (n < 3) {
            return false;
        }
        
        int[] low = new int[n];
        int right = nums[n - 1];
        int left = nums[0];
        for (int i = 1; i < n; ++i) {
            if (nums[i] > left) {
                low[i] = 1;
            } else if (nums[i] < left) {
                left = nums[i];
            }
        }
        for (int i = n - 2; i >= 0; --i) {
            if (nums[i] < right) {
                if (low[i] == 1) {
                    return true;
                }
            } else if (nums[i] > right) {
                right = nums[i];
            }
        }
        
        return false;
    }
}

如果要用O(1)空间复杂度，则只能有有限变量。命名两个变量low和mid，用贪心算法不断更新两者。本来应该想到这个方法的

class Solution {
    public boolean increasingTriplet(int[] nums) {
        int n = nums.length;
        if (n < 3) {
            return false;
        }
        int low = nums[0];
        int mid = nums[0];
        
        for (int i = 1; i < n; ++i) {
            if (nums[i] > mid) {
                if (mid == low) {
                    mid = nums[i];
                } else {
                    return true;
                }
            } else if (nums[i] > low && nums[i] < mid) {
                mid = nums[i];
            } else if (nums[i] < low) {
                if (low == mid) {
                    low = mid = nums[i];
                } else {
                    low = nums[i];
                }
            }
        }
        
        return false;
    }
}

---

• https://leetcode.com/problems/increasing-triplet-subsequence/