334 Increasing Triplet Subsequence
找出数组中是否存在n个连续增长数列
my solution (0ms, 100%)
这道题的解法来自于在做完另一道题后, 观察最佳算法时获得的技巧
简单来说, 这可以用一个可覆写的数组来实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| func increasingTriplet(nums []int) bool {
vec := []int{1 << 63 - 1}
for _, v := range nums {
if v > vec[len(vec) - 1] {
vec = append(vec, v)
if len(vec) > 2 {
return true
}
continue
}
for i, v2 := range vec {
if v <= v2 {
vec[i] = v
break
}
}
}
return false
}
|
因为答案仅仅需要一个 bool 值, 所以可以这么做
不过, 有时候, vec 的值会是错误的, 同时这个解可以用于 n 个数字, 也可用于递减数组
(同时, 如果我在讨论中, 没有看到相应语言完全比我好的解法, 我会开始分享自己的解法)
(https://leetcode.com/problems/increasing-triplet-subsequence/discuss/298228/go-simple-solution-O(n)-100)
开始没想到, 尝试了几次之后想到的
best solution
1
2
3
4
5
6
7
8
9
10
11
12
13
| func increasingTriplet(nums []int) bool {
min1,min2:= 2<<32-1,2<<32-1
for _,v:=range nums{
if v<=min1{
min1=v
}else if v<=min2{
min2=v
}else {
return true
}
}
return false
}
|
EHM… 我好像又把问题复杂化了…
不过没关系, 我的解可以用于 n 个序列 (我如此安慰自己)