334. Increasing Triplet Subsequence

Traverse

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public boolean increasingTriplet(int[] nums) {
        int[] leftMin = new int[nums.length]; // 左侧至当前下标（含）的最小值
        leftMin[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            leftMin[i] = Math.min(nums[i], leftMin[i - 1]);
        }

        int[] rightMax = new int[nums.length]; // 右侧至当前下标（含）的最大值
        rightMax[rightMax.length - 1] = nums[nums.length - 1];
        for (int i = nums.length - 2; i >= 0; i--) {
            rightMax[i] = Math.max(nums[i], rightMax[i + 1]);
        }

        for (int i = 1; i < nums.length - 1; i++) {
            // 注意此处比较的为 leftMin[i - 1] 与 rightMax[i + 1]
            if (nums[i] > leftMin[i - 1] && nums[i] < rightMax[i + 1]) {
                return true;
            }
        }

        return false;
    }
}

Greedy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean increasingTriplet(int[] nums) {
        if (nums.length < 3) {
            return false;
        }

        int first = nums[0], second = Integer.MAX_VALUE;
        for (int i = 1; i < nums.length; i++) {
            int num = nums[i];
            if (num > second) {
                return true;
            } else if (num > first) {
                second = num;
            } else {
                first = num;
            }
        }

        return false;
    }
}

References

334. Increasing Triplet Subsequence