【Leetcode解題】334. Increasing Triplet Subsequence

題目

• 題目連結
• 目標函式 : increasingTriplet(nums)
  • Input : nums: List[int]
  • Output : bool

解題概念

• 題意 :
  • 給予一陣列 nums，如果滿足以下條件 :
    1. i < j < k
    2. nums[i] < nums[j] < nums[k]
  • 則回傳 True，否則回傳 False

我的寫法

• 想法 :
  1. 用三重 for 迴圈，分別針對 i, j, i :
     • 若滿足 nums[i] < nums[j] and nums[j] < nums[k] ，直接回傳 True
  2. 若迴圈結束，代表找不到，則回傳 False
• 程式碼 :

  if len(nums) < 3:
      return False
  for i in range(0, len(nums)-2):
      for j in range(i, len(nums)-1):
          for k in range(j, len(nums)):
              if nums[i] < nums[j] and nums[j] < nums[k]:
                  return True
  return False

• 成效 : Runtime Error
  • 因為此算法之時間複雜度為 $O(n^3)$

解答 or 其他優秀寫法

• 想法 :
  1. left 存放目標的 nums[i]、mid 存放目標的 nums[j]
  2. 透過 for 迴圈針對每個 num，會有三種狀況 :
     1. 若 num > mid，代表有一數大於 left 與 mid，已滿足題目所求，故直接回傳 True
     2. 若 num > left and num < mid，代表有一數介於 left 與 mid 之間，故把該值設為 mid (希望後續能找到比該值更大的 nums[k])
     3. 若 num < left，代表有一數小於 left 與 mid，故把該值設為 left(希望後續能找到比該值更大的 nums[j] 與 nums[k])
• 程式碼 :

  if len(nums) < 3:
      return False    
  left = 2 ^ 32
  mid = 2 ^ 32
      
  for num in nums:
      if num > mid:
          return True
      elif num > left and num < mid:
          mid = num
      elif num < left:
          left = num
              
  return False

• 成效 :
  • Runtime: 781 ms (faster than 62.76%)
  • Memory Usage: 22.9 M (less than 51.86%)