第五章 - 高频考题(中等)
1906. 查询差绝对值的最小值
0334. 递增的三元子序列

题目地址(334. 递增的三元子序列)

题目描述

1
给定一个未排序的数组,判断这个数组中是否存在长度为 3 的递增子序列。
2
3
数学表达式如下:
4
5
如果存在这样的 i, j, k, 且满足 0 ≤ i < j < k ≤ n-1,
6
使得 arr[i] < arr[j] < arr[k] ,返回 true ; 否则返回 false 。
7
说明: 要求算法的时间复杂度为 O(n),空间复杂度为 O(1) 。
8
9
示例 1:
10
11
输入: [1,2,3,4,5]
12
输出: true
13
示例 2:
14
15
输入: [5,4,3,2,1]
16
输出: false
Copied!

前置知识

  • 双指针

公司

  • 百度
  • 字节

思路

这道题是求解顺序数字是否有三个递增的排列, 注意这里没有要求连续的,因此诸如滑动窗口的思路是不可以的。
题目要求 O(n)的时间复杂度和 O(1)的空间复杂度,因此暴力的做法就不用考虑了。
我们的目标就是依次找到三个数字,其顺序是递增的。
因此我们的做法可以是从左到右依次遍历,然后维护三个变量,分别记录最小值,第二小值,第三小值。只要我们能够填满这三个变量就返回 true,否则返回 false。
334.increasing-triplet-subsequence

关键点解析

  • 维护两个变量,分别记录最小值,第二小值。只要我们能够填满这三个变量就返回 true,否则返回 false

代码

代码支持: JS, Python3
JS Code:
1
/*
2
/**
3
* @param {number[]} nums
4
* @return {boolean}
5
*/
6
var increasingTriplet = function (nums) {
7
if (nums.length < 3) return false;
8
let n1 = Number.MAX_VALUE;
9
let n2 = Number.MAX_VALUE;
10
11
for (let i = 0; i < nums.length; i++) {
12
if (nums[i] <= n1) {
13
n1 = nums[i];
14
} else if (nums[i] <= n2) {
15
n2 = nums[i];
16
} else {
17
return true;
18
}
19
}
20
21
return false;
22
};
Copied!
Python3 Code:
1
class Solution:
2
def increasingTriplet(self, A: List[int]) -> bool:
3
a1 = a2 = float("inf")
4
5
for a in A:
6
if a > a2:
7
return True
8
elif a > a1:
9
a2 = a
10
else:
11
a1 = a
12
return False
Copied!
复杂度分析
  • 时间复杂度:$O(N)$
  • 空间复杂度:$O(1)$
大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。