題目

  • 題目連結
  • 目標函式 : countSubarrays(nums, minK, maxK)
    • Input : nums: List[int]、minK: int、maxK: int
    • Output : int

解題概念

  • 題意 : 給予一陣列 nums，找出其 Subarray 的數量，且那些 Subarray 須滿足 :
    • Subarray 中的最小值 = minK
    • Subarray 中的最大值 = maxK

我的寫法

  • 想法 :
    • 利用雙重 for 迴圈之 i 與 j，去判斷 nums[i] ~ nums[j] 是否為滿足條件的 Subarray
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    def satisfy(arr): # 判斷是否滿足條件
        if arr == []:
            return False
        if max(arr) == maxK and min(arr) == minK:
            return True
        return False

    cnt = 0
    for i in range(0, len(nums)):
        for j in range(0, len(nums)):
            if satisfy(nums[i:j+1]):
                cnt += 1
    return cnt
  • 成效 : Runtime Error
    • Time Complexity : $\color{DB4D6D}{O(n^2)}$

解答 or 其他優秀寫法

  • 想法 :
    1. 變數設定 :
      • lastseenmax : 之前看到在 nums 中出現 maxK 的 index
      • lastseenmin : 之前看到在 nums 中出現 minK 的 index
      • subArrayStartIndex : 當前 Subarray 開始的 Index
    2. 利用 for 迴圈去抓 num，並有三種狀況需要處理 :
      1. 當 num < minK or num > maxK :
        • 代表當前的 num 不會形成任何 Subarray (因為題目要求之 Subarray 需要是 contiguous)
        • 因此，要將 lastseenmax 與 lastseenmin 從新計算(即設為初始值 = -1)
        • 另外也要將 subArrayStartIndex 設為 i + 1，下一回合從新開始計算 Subarray
      2. 當 num == minK :
        • 需將 minK 修正成 i
      3. 當 num = maxK :
        • 需將 maxK 修正成 i
      4. 三種狀況處理完後，計算出當前 Subarray 包含所有可能滿足條件之狀況數量
        • EX : 當前狀況如下圖
        • 下圖滿足條件的 Subarray有 : [2, 4, 1, 3, 5]、[4, 1, 3, 5]、[1, 3, 5]，共 3 種
        • 而扣除掉黃色的部分，其他兩個數字會影響到數量的計算
          • 其他狀況 : 若黃色後面還有其他數字 (即 i 不是指在 Boundary 上)，那些數字並不會影響到本回合之計算，因為「若扣除那些數字之 Subarray」的狀況早已在 i 指在 Boundary時已計算進去，因此這裡無須重複計算
        • 也就是「整個 Subarray 的長度 - 兩個 Bound 圍起來的範圍長度 = 多出來的數量」，再加上兩個 Bound 圍起來的部分本身，所以共有 (整個 Subarray 的長度 - 兩個 Bound 圍起來的範圍長度 + 1) 個可能性
        • 總結來看，可推得以下公式 : > 若該值 < 0 ，則讓其 = 0
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    res = 0
    subArrayStartIndex = 0
    lastseenmin = -1
    lastseenmax = -1

    for i in range(0, len(nums)):
        num = nums[i]
        if num < minK or num > maxK:
            lastseenmin = -1
            lastseenmax = -1
            subArrayStartIndex = i + 1
                
        if num == minK:
            lastseenmin = i
        if num == maxK:
            lastseenmax = i
        
        res += max(min(lastseenmin, lastseenmax) - subArrayStartIndex + 1, 0)
                
    return res
  • 成效 :
    • Time Complexity : $\color{DB4D6D}{O(n)}$
    • Runtime: Unknown (Don’t have enough accepted submissions)
    • Memory Usage: Unknown (Don’t have enough accepted submissions)