是否存在長度為3的遞增子序列 Increasing Triplet Subsequence_Leetcode 精選75題

Kanhaiya Sharma on Unsplash

題目敘述

題目會給我們一個輸入陣列nums，要求我們判斷輸入陣列nums內部是否存在長度為三的遞增子序列?

題目的原文敘述

測試範例

Example 1:

Input: nums = [1,2,3,4,5]
Output: true
Explanation: Any triplet where i < j < k is valid.

Example 2:

Input: nums = [5,4,3,2,1]
Output: false
Explanation: No triplet exists.

Example 3:

Input: nums = [2,1,5,0,4,6]
Output: true
Explanation: The triplet (3, 4, 5) is valid because nums[3] == 0 < nums[4] == 4 < nums[5] == 6.

約束條件

Constraints:

• 1 <= nums.length <= 5 * 10^5
• -2^31 <= nums[i] <= 2^31 - 1

演算法

這題是問存在與否，也就是找到一條長度為三的遞增子序列就算存在。

除了第一直覺的立方等級的暴力搜索演算法之外，其實還有一個更巧妙的O(n)線性時間演算法。

題目已經指定長度為三的遞增子序列，也就是說，抽象化的表達，可以這樣描述

Small, Medium, Large分別代表小、中、大三個元素，
其中 Small 小< Medium 中< Large 大。

一開始都初始化成無窮大，接著開始從左到右線性掃描，如果遇到比Small還小的數字，就更新 Small為更小的值。

同樣的道理，如果遇到比Small大但是比Medium還小的數字，就更新 Medium為更小的值。

最後，假如遇到比Small大也比Medium還大的數字，代表我們已經找到Large了，這時候，長度為三的遞增子序列分別就是Small, Medium和Large。

範例和概念示意圖:

image