from typing import List
# 這道題我是用動態規劃的方法來做的，
# 時間復雜度是O(n~2)空間復雜度是O（n），
# 定義一個串列，其中用來存放當前數比前面幾個數遞增大，
class Solution:
def increasingTriplet(self, nums: List[int]) -> bool:
# 如果串列沒喲三個數，直接回傳False
if len(nums) < 3 :return False
# 定義一個串列，用來表示動態方程，這里將他們的初始值都設定成1
dp = [1 for i in range(len(nums))]
# 進行遍歷
for index1 in range(1,len(nums)):
# 把當前數都和前邊的數作比較，如果比某一個數大，就在它的基礎上加上一
for index2 in range(0,index1):
# 這里dp上每一個位置，都表示這個數比前邊幾個遞增數大，
if nums[index1] > nums[index2]:
dp[index1] = max(dp[index1],dp[index2] + 1)
#如果有遞增三元組，就回傳真，這樣后邊的就不用了遍歷了
if dp[index1] >= 3:return True
# 全部遍歷完成，沒有退出函式，就回傳false
else:
return False
A = Solution()
print(A.increasingTriplet([1,2,3,4,5]))
print(A.increasingTriplet([4,5,4,4]))
print(A.increasingTriplet([1,2,-10,-8,-7]))
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/65154.html
標籤：Python