未分類

Increasing Triplet Subsequence

Go, LeetCode, LongestIncreasingSubsequence

Increasing Triplet Subsequence

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should:

Return true if there exists i, j, k

such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.

Your algorithm should run in O(n) time complexity and O(1) space complexity.

For examples:

1
2
3
4
5
Given [1, 2, 3, 4, 5],
return true.
Given [5, 4, 3, 2, 1],
return false.

Default:

1
2
3
func increasingTriplet(nums []int) bool {
}

解答思路:

最初看到題目是想到Longest Increasing Subsequence的做法，然而這次只要確認是否存在至少有三個元素的遞增子數列，所以肯定是比先前簡單多了，只要一邊遍歷一邊找出最小且不重覆的兩個值，當再取出的值比目前所找到的兩個值都來的大，就可以直接回傳true(此三個元素能組出遞增子數列)，否則到最後遍歷結束若還是沒有找到較大的值才回傳false。

程式碼解說:

因為要找出最小且不重覆的兩個值，所以一開始便初始化兩個極大值以找出兩個最小值，接著一邊遍歷一邊判斷，當取出的值比最小值還小或相等則將其取代，取出的值比第二小的值還小或相等同樣也是做取代，而當再取出的值比目前所找到的兩個值都來的大，就可以直接回傳true(此三個元素能組出遞增子數列)，否則到最後遍歷結束若還是沒有找到較大的值才回傳false

1
2
3
4
5
6
7
8
9
10
11
12
A := math.MaxInt32
B := math.MaxInt32
for _, v := range nums {
	if v <= A {
		A = v
	} else if v <= B {
		B = v
	} else {
		return true
	}
}
return false

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func increasingTriplet(nums []int) bool {
	A := math.MaxInt32
	B := math.MaxInt32
	for _, v := range nums {
		if v <= A {
			A = v
		} else if v <= B {
			B = v
		} else {
			return true
		}
	}
	return false
}

總結:

要確認是否存在至少有三個元素的遞增子數列(詳細規則請看題目)，只要一邊遍歷一邊找出最小且不重覆的兩個值，當再取出的值比目前所找到的兩個值都來的大，就可以直接回傳true(此三個元素能組出遞增子數列)，否則到最後遍歷結束若還是沒有找到較大的值才回傳false。

分享到