334. Increasing Triplet Subsequence - python3

2092 ワード

334. Increasing Triplet Subsequence


Given an integer array nums, return true if there exists a triple of indices (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k]. If no such indices exists, return false.
class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        for i in range(len(nums)-2):
            if nums[i] < nums[i+1] and nums[i+1] < nums[i+2]:
                return True

        return False
最初は3回連続でいいと思ってたけど、違う

My Answer 1: Accepted (Runtime: 3968 ms - 7.99% / Memory Usage: 14.8MB - 49.89%)

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        for i in range(len(nums)-2):
            numlist = []
            for j in range(i+1, len(nums)):
                if nums[i] < nums[j]:
                    numlist.append(nums[j])
            for j in range(len(numlist)-1):
                if numlist[j] < numlist[j+1]:
                    return True

        return False
7運行時の主人公の中にFor Moon.^^
  • 各数値の自己より大きい値をnumlistに
  • 記憶する.
  • numlistにnumlist[j] < numlist[j+1]がある場合、True Return
  • ディック・シャナリーでやってみましたが・・・汚れる

    Time Complexity:O(n) and Space:O(1)


    Solution 1: Runtime: 56 ms - 57.56% / Memory Usage: 14.7 MB - 93.66%

    class Solution:
        def increasingTriplet(self, nums: List[int]) -> bool:
            f_min = float('inf')
            s_min = float('inf')
            for i in range(len(nums)):
                if nums[i] <= f_min:
                    f_min = nums[i]
                elif nums[i] <= s_min:
                    s_min = nums[i]
                else:
                    return True
            return False
    f minとs minで無限値に初期化し、第1、第2の最大値を検索します.
  • when nums[i] <= first_min, update first_min with nums[i]
  • when first_min < nums[i] <= second_min, update second_min with nums[i]
  • when nums[i] > second_min, good! we find the third element!