0334-递增的三元子序列

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 15:35:39 2023-09-13 15:35:39 Updated    

给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。

如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回
true ；否则，返回 false 。

示例 1：

**输入：** nums = [1,2,3,4,5]
**输出：** true
**解释：** 任何 i < j < k 的三元组都满足题意

示例 2：

**输入：** nums = [5,4,3,2,1]
**输出：** false
**解释：** 不存在满足题意的三元组

示例 3：

**输入：** nums = [2,1,5,0,4,6]
**输出：** true
**解释：** 三元组 (3, 4, 5) 满足题意，因为 nums[3] == 0 < nums[4] == 4 < nums[5] == 6

提示：

  • 1 <= nums.length <= 5 * 105
  • -231 <= nums[i] <= 231 - 1

进阶： 你能实现时间复杂度为 O(n) ，空间复杂度为 O(1) 的解决方案吗？

方法一：双向遍历

如果数组 nums 中存在一个下标 $i$ 满足 $1 \le i < n - 1$，使得在 nums}[i]$ 的左边存在一个元素小于 nums}[i]$ 且在 nums}[i]$ 的右边存在一个元素大于 nums}[i]$，则数组 nums 中存在递增的三元子序列。

在 nums}[i]$ 的左边存在一个元素小于 nums}[i]$ 等价于在 nums}[i]$ 的左边的最小元素小于 nums}[i]$，在 nums}[i]$ 的右边存在一个元素大于 nums}[i]$ 等价于在 nums}[i]$ 的右边的最大元素大于 nums}[i]$，因此可以维护数组 nums 中的每个元素左边的最小值和右边的最大值。

创建两个长度为 $n$ 的数组 leftMin 和 rightMax，对于 $0 \le i < n$，leftMin}[i]$ 表示 nums}[0]$ 到 nums}[i]$ 中的最小值，rightMax}[i]$ 表示 nums}[i]$ 到 nums}[n - 1]$ 中的最大值。

数组 leftMin 的计算方式如下：

  • leftMin}[0] = \textit{nums}[0]$；

  • 从左到右遍历数组 nums，对于 $1 \le i < n$，leftMin}[i] = \min(\textit{leftMin}[i - 1], \textit{nums}[i])$。

数组 rightMax 的计算方式如下：

  • rightMax}[n - 1] = \textit{nums}[n - 1]$；

  • 从右到左遍历数组 nums，对于 $0 \le i < n - 1$，rightMax}[i] = \max(\textit{rightMax}[i + 1], \textit{nums}[i])$。

得到数组 leftMin 和 rightMax 之后，遍历 $1 \le i < n - 1$ 的每个下标 $i$，如果存在一个下标 $i$ 满足 leftMin}[i - 1] < \textit{nums}[i] < \textit{rightMax}[i + 1]$，则返回 true，如果不存在这样的下标 $i$，则返回 false。

[sol1-Java]
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 n = nums.length;
        if (n < 3) {
            return false;
        }
        int[] leftMin = new int[n];
        leftMin[0] = nums[0];
        for (int i = 1; i < n; i++) {
            leftMin[i] = Math.min(leftMin[i - 1], nums[i]);
        }
        int[] rightMax = new int[n];
        rightMax[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], nums[i]);
        }
        for (int i = 1; i < n - 1; i++) {
            if (nums[i] > leftMin[i - 1] && nums[i] < rightMax[i + 1]) {
                return true;
            }
        }
        return false;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    public bool IncreasingTriplet(int[] nums) {
        int n = nums.Length;
        if (n < 3) {
            return false;
        }
        int[] leftMin = new int[n];
        leftMin[0] = nums[0];
        for (int i = 1; i < n; i++) {
            leftMin[i] = Math.Min(leftMin[i - 1], nums[i]);
        }
        int[] rightMax = new int[n];
        rightMax[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.Max(rightMax[i + 1], nums[i]);
        }
        for (int i = 1; i < n - 1; i++) {
            if (nums[i] > leftMin[i - 1] && nums[i] < rightMax[i + 1]) {
                return true;
            }
        }
        return false;
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int n = nums.size();
        if (n < 3) {
            return false;
        }
        vector<int> leftMin(n);
        leftMin[0] = nums[0];
        for (int i = 1; i < n; i++) {
            leftMin[i] = min(leftMin[i - 1], nums[i]);
        }
        vector<int> rightMax(n);
        rightMax[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = max(rightMax[i + 1], nums[i]);
        }
        for (int i = 1; i < n - 1; i++) {
            if (nums[i] > leftMin[i - 1] && nums[i] < rightMax[i + 1]) {
                return true;
            }
        }
        return false;
    }
};
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#define MIN(a, b) ((a) > (b) ? (b) : (a))
#define MAX(a, b) ((a) < (b) ? (b) : (a))

bool increasingTriplet(int* nums, int numsSize){
    if (numsSize < 3) {
        return false;
    }
    int * leftMin = (int *)malloc(sizeof(int) * numsSize);
    int * rightMax = (int *)malloc(sizeof(int) * numsSize);
    leftMin[0] = nums[0];
    for (int i = 1; i < numsSize; i++) {
        leftMin[i] = MIN(leftMin[i - 1], nums[i]);
    }
    rightMax[numsSize - 1] = nums[numsSize - 1];
    for (int i = numsSize - 2; i >= 0; i--) {
        rightMax[i] = MAX(rightMax[i + 1], nums[i]);
    }
    for (int i = 1; i < numsSize - 1; i++) {
        if (nums[i] > leftMin[i - 1] && nums[i] < rightMax[i + 1]) {
            return true;
        }
    }
    free(leftMin);
    free(rightMax);
    return false;
}
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
func increasingTriplet(nums []int) bool {
    n := len(nums)
    if n < 3 {
        return false
    }
    leftMin := make([]int, n)
    leftMin[0] = nums[0]
    for i := 1; i < n; i++ {
        leftMin[i] = min(leftMin[i-1], nums[i])
    }
    rightMax := make([]int, n)
    rightMax[n-1] = nums[n-1]
    for i := n - 2; i >= 0; i-- {
        rightMax[i] = max(rightMax[i+1], nums[i])
    }
    for i := 1; i < n-1; i++ {
        if nums[i] > leftMin[i-1] && nums[i] < rightMax[i+1] {
            return true
        }
    }
    return false
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

func max(a, b int) int {
    if b > a {
        return b
    }
    return a
}
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        n = len(nums)
        if n < 3:
            return False
        leftMin = [0] * n
        leftMin[0] = nums[0]
        for i in range(1, n):
            leftMin[i] = min(leftMin[i - 1], nums[i])
        rightMax = [0] * n
        rightMax[n - 1] = nums[n - 1]
        for i in range(n - 2, -1, -1):
            rightMax[i] = max(rightMax[i + 1], nums[i])
        for i in range(1, n - 1):
            if leftMin[i - 1] < nums[i] < rightMax[i + 1]:
                return True
        return False
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var increasingTriplet = function(nums) {
    const n = nums.length;
    if (n < 3) {
        return false;
    }
    const leftMin = new Array(n).fill(0);
    leftMin[0] = nums[0];
    for (let i = 1; i < n; i++) {
        leftMin[i] = Math.min(leftMin[i - 1], nums[i]);
    }
    const rightMax = new Array(n).fill(0);
    rightMax[n - 1] = nums[n - 1];
    for (let i = n - 2; i >= 0; i--) {
        rightMax[i] = Math.max(rightMax[i + 1], nums[i]);
    }
    for (let i = 1; i < n - 1; i++) {
        if (nums[i] > leftMin[i - 1] && nums[i] < rightMax[i + 1]) {
            return true;
        }
    }
    return false;
};

复杂度分析

  • 时间复杂度：$O(n)$，其中 $n$ 是数组 nums 的长度。需要遍历数组三次。

  • 空间复杂度：$O(n)$，其中 $n$ 是数组 nums 的长度。需要创建两个长度为 $n$ 的数组 leftMin 和 rightMax。

方法二：贪心

可以使用贪心的方法将空间复杂度降到 $O(1)$。从左到右遍历数组 nums，遍历过程中维护两个变量 first 和 second，分别表示递增的三元子序列中的第一个数和第二个数，任何时候都有 first} < \textit{second。

初始时，first} = \textit{nums}[0]$，second} = +\infty$。对于 $1 \le i < n$，当遍历到下标 $i$ 时，令 num} = \textit{nums}[i]$，进行如下操作：

  1. 如果 num} > \textit{second，则找到了一个递增的三元子序列，返回 true；

  2. 否则，如果 num} > \textit{first，则将 second 的值更新为 num；

  3. 否则，将 first 的值更新为 num。

如果遍历结束时没有找到递增的三元子序列，返回 false。

上述做法的贪心思想是：为了找到递增的三元子序列，first 和 second 应该尽可能地小，此时找到递增的三元子序列的可能性更大。

假设 $(\textit{first}, \textit{second}, \textit{num})$ 是一个递增的三元子序列，如果存在 second’ 满足 first} < \textit{second’} < \textit{second 且 second’ 的下标位于 first 的下标和 num 的下标之间，则 $(\textit{first}, \textit{second’}, \textit{num})$ 也是一个递增的三元子序列。但是当 $(\textit{first}, \textit{second’}, \textit{num})$ 是递增的三元子序列时，由于 num 不一定大于 second，因此 $(\textit{first}, \textit{second}, \textit{num})$ 未必是递增的三元子序列。由此可见，为了使找到递增的三元子序列的可能性更大，三元子序列的第二个数应该尽可能地小，将 second’ 作为三元子序列的第二个数优于将 second 作为三元子序列的第二个数。

同理可得，三元子序列的第一个数也应该尽可能地小。

如果遍历过程中遇到的所有元素都大于 first，则当遇到 num} > \textit{second 时，first 一定出现在 second 的前面，second 一定出现在 num 的前面，$(\textit{first}, \textit{second}, \textit{num})$ 即为递增的三元子序列。

如果遍历过程中遇到小于 first 的元素，则会用该元素更新 first，虽然更新后的 first 出现在 second 的后面，但是在 second 的前面一定存在一个元素 first’ 小于 second，因此当遇到 num} > \textit{second 时，$(\textit{first’}, \textit{second}, \textit{num})$ 即为递增的三元子序列。

根据上述分析可知，当遇到 num} > \textit{second 时，一定存在一个递增的三元子序列，该三元子序列的第二个数和第三个数分别是 second 和 num，因此返回 true。

[sol2-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean increasingTriplet(int[] nums) {
        int n = nums.length;
        if (n < 3) {
            return false;
        }
        int first = nums[0], second = Integer.MAX_VALUE;
        for (int i = 1; i < n; i++) {
            int num = nums[i];
            if (num > second) {
                return true;
            } else if (num > first) {
                second = num;
            } else {
                first = num;
            }
        }
        return false;
    }
}
[sol2-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public bool IncreasingTriplet(int[] nums) {
        int n = nums.Length;
        if (n < 3) {
            return false;
        }
        int first = nums[0], second = int.MaxValue;
        for (int i = 1; i < n; i++) {
            int num = nums[i];
            if (num > second) {
                return true;
            } else if (num > first) {
                second = num;
            } else {
                first = num;
            }
        }
        return false;
    }
}
[sol2-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int n = nums.size();
        if (n < 3) {
            return false;
        }
        int first = nums[0], second = INT_MAX;
        for (int i = 1; i < n; i++) {
            int num = nums[i];
            if (num > second) {
                return true;
            } else if (num > first) {
                second = num;
            } else {
                first = num;
            }
        }
        return false;
    }
};
[sol2-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool increasingTriplet(int* nums, int numsSize){
    if (numsSize < 3) {
        return false;
    }
    int first = nums[0], second = INT_MAX;
    for (int i = 1; i < numsSize; i++) {
        int num = nums[i];
        if (num > second) {
            return true;
        } else if (num > first) {
            second = num;
        } else {
            first = num;
        }
    }
    return false;
}
[sol2-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func increasingTriplet(nums []int) bool {
    n := len(nums)
    if n < 3 {
        return false
    }
    first, second := nums[0], math.MaxInt32
    for i := 1; i < n; i++ {
        num := nums[i]
        if num > second {
            return true
        } else if num > first {
            second = num
        } else {
            first = num
        }
    }
    return false
}
[sol2-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        n = len(nums)
        if n < 3:
            return False
        first, second = nums[0], float('inf')
        for i in range(1, n):
            num = nums[i]
            if num > second:
                return True
            if num > first:
                second = num
            else:
                first = num
        return False
[sol2-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var increasingTriplet = function(nums) {
    const n = nums.length;
    if (n < 3) {
        return false;
    }
    let first = nums[0], second = Number.MAX_VALUE;
    for (let i = 1; i < n; i++) {
        const num = nums[i];
        if (num > second) {
            return true;
        } else if (num > first) {
            second = num;
        } else {
            first = num;
        }
    }
    return false;
};

复杂度分析

  • 时间复杂度：$O(n)$，其中 $n$ 是数组 nums 的长度。需要遍历数组一次。

  • 空间复杂度：$O(1)$。

 Comments
On this page
0334-递增的三元子序列