Python描述 LeetCode 334. 遞增的三元子序列

大家好，我是亓官劼（qí guān jié ），在【亓官劼】公眾號、CSDN、GitHub、B站等平台分享一些技術博文，主要包括前端開發、python後端開發、小程序開發、數據結構與算法、docker、Linux常用運維、NLP等相關技術博文，時光荏苒，未來可期，加油~

如果喜歡博主的文章可以關注博主的個人公眾號【亓官劼】(qí guān jié)，裡面的文章更全更新更快。如果有需要找博主的話可以在公眾號後台留言，我會盡快回復消息.

---

本文原創為【亓官劼】（qí guān jié ），請大家支持原創，部分平台一直在惡意盜取博主的文章！！！ 全部文章請關注微信公眾號【亓官劼】。

題目

給你一個整數數組 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) 的解決方案嗎？

Python描述

參考了宮水三葉的解法。f維護一個升序且每個數字盡可能小的序列，這裡由於只需要長度為3的序列，我們簡化判斷，只維護2個就好。宮水三葉的這種思路在求最長升序序列的時候很贊。

class Solution:
def increasingTriplet(self, nums: List[int]) -> bool:
n = len(nums)
f = [2**31-1,2**31-1] # 維護一個升序且每個數字盡可能小的序列
for i in range(n):
t = nums[i]
if t > f[1]:
return True
elif f[0] < t < f[1]:
f[1] = t
elif f[0] > t:
f[0] = t
return False