1 題目描述

這是我的第一次參加 LeetCode Contest，這次的題目是一道簡單的滑動窗口問題，給定一個數組nums和一個整數k，你需要針對大小為 k 的所有子陣列計算它們的 “power”：

1. 如果子陣列的所有元素是連續且按升序排列，則該子陣列的 power 是其最大元素。
2. 如果子陣列的元素不符合條件，則返回 -1。

2 解法

2.1 我的解法

我一開始的想法很簡單，我需要有一個function負責檢查是否為連續且按升序排列，如果是就返回最後一個數值，如果不是就返回-1。

1
2
3
4
5

def helper(sub_nums: List[int]) -> int:
    for j in range(1, k):
        if sub_nums[j - 1] + 1 != sub_nums[j]:
            return -1
    return sub_nums[-1]

接下來我們只要根據 k 的長度，把數組分成大小為 k 的子陣列，然後檢查每個子陣列是否符合條件，如果符合就找出最大值，如果不符合就返回-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

def resultsArray(self, nums: List[int], k: int) -> List[int]:
    """
    N = len(nums)

    time: O(N*K)
    space: O(N-k+1)
    """
    def helper(sub_nums: List[int]) -> int:
        for j in range(1, k):
            if sub_nums[j - 1] + 1 != sub_nums[j]:
                return -1
        return sub_nums[-1]

    ans = []
    for i in range(len(nums)):
        if i + k <= len(nums):
            ans.append(helper(nums[i:i + k]))
    return ans

但是以上的時間複雜度是 O(N*K)，有沒有辦法可以得到時間複雜度是 O(N) 呢？

2.2 進階解法

他有個很重要的概念，什麼樣的狀況可以是可以紀錄當前的值，而非 -1 呢？
所謂的合格是，兩個值，要連續且按升序排列

1. 當前的值，與前一個值相差 1（合格）
2. 並且，過去從i - k開始，往後的數值到 i 為止，都是連續且按升序排列

當時我看到有個人的解法是，他用了一個變數bad來記錄，從上面的條件來看，如果當前的值不是連續升序時，這個影響必須後面連續 k 個值，只有在被影響的要素慢慢消除時，才可以反回當前的值（也就是最大值），從這裡可以看到就有點像是一個累積毒素的感覺。

1. 當檢查到當下的值不符合條件時，我們就要把bad的值+1，這就身體沈澱的毒素。
2. 那我們什麼時候變得健康呢？那就是當我們的毒素都清理乾淨後bad==0。
   • 我們要確保前面從 i - k 開始到i的都沒有毒素，如果遇到毒素
   • 其實只要bad不要增加持續一段時間即可，也就是說當遇到毒素時，bad+=1當遇到健康的時候bad-=1
3. bad可能會有2種狀態
   • bad > 0：代表我們有毒素，因此我們要回傳-1
   • bad == 0：代表我們健康，我們要紀錄當前的值nums[i]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

def resultsArray3(self, nums: List[int], k: int) -> List[int]:
    # 如果 k == 1，直接返回 nums 即為答案
    if k == 1:
        return nums
    bad = 0
    res = []
    # 從 1 開始，因為我們要從第二個數字開始往後比較
    for i in range(1, len(nums)):
        # 健康當前是健康的
        if nums[i] - 1 == nums[i - 1]:
            # 但是身體有毒素 bad > 0，因爲當下是健康的，所以毒素-1
            if bad > 0:
                bad -= 1
        else:
            # 不健康！如果當前的值不是連續升序，我們就要增加毒素
            bad += 1
        
        # 從 k - 1 開始記錄 
        if i >= k - 1:
            # 如果毒素為 0，代表我們健康，記錄當前的值否則返回 -1
            res.append(nums[i] if bad == 0 else -1)

    return res

上面的邏輯可能會通過題目的三個測試，但是如果我們碰到[5, 5, 5, 5, 5, 1, 2, 3, 4] 就是前面簡直就是垃圾人生，吃一堆毒素…，導致後面儘管很健康，但是也清理不掉毒素，可是這不是我們要的結果！我們希望，只要確保前k個值沒有毒素就好。

從上圖來看，我們希望i=7時，bad是歸零的狀態因為[1, 2, 3]是合法的，當bad==0時我們才可以把nums[7]塞到res裡面。這意味著，為了確保遍歷到i=7時bad是歸零的，也就是說我們上面的程式碼要對bad+=1的時機做調整。

你會看到上圖中，我們共畫了5個箭頭，我們要知道只要確保前k個值沒有毒素就好，也就是說如果毒素離i太遠，就會自動代謝掉，就是要毒素自動-1。

• 從i=3時bad已經累積了3(1+1+1)個毒素
  • 我們往前看距離k的位置i=1時，發現當時毒素有+1
  • 但是其實i=1已經距離i=4太遠了！這個毒素的影響性應該要代謝掉
  • 我們只關心前k個值是否有毒素，所以我們這時候應該 -1把這個太過於遙遠的毒素代謝掉
  • 最後bad變成(1+1+1)-1=2
• 從i=4時bad此時是3(2+1)
  • 因為上一個殘留的毒素是2，加上當前i=4是不健康的所以+1
  • 我們往前看距離k的位置i=2時，發現當時毒素有+1
  • 但是其實i=2已經距離i=5太遠了！這個毒素的影響性應該要被代謝掉了
  • 我們只關心前k個值是否有毒素，所以我們這時候應該 -1，把這個太過於遙遠的毒素代謝掉
  • 最後bad變成(2+1)-1=2
• 從i=5時bad此時仍是3(2+1)
  • 因為上一個殘留的毒素是2，加上當前i=5是不健康的所以+1
  • 我們往前看距離k的位置i=3時，發現當時毒素有+1，但是其實i=3已經距離i=6太遠了！這個毒素的影響性應該要代謝掉
  • 我們只關心前k個值是否有毒素，所以我們這時候應該 -1，把這個太過於遙遠的毒素代謝掉
  • 最後bad變成(2+1)-1=2
• 從i=6時bad此時是2(2+0)
  • 因為上一個殘留的毒素是2，加上當前i=6是健康的所以+0
  • 我們往前看距離k的位置i=4時，發現當時毒素有+1，但是其實i=4已經距離i=6太遠了！這個毒素的影響性應該要代謝掉
  • 我們只關心前k個值是否有毒素，所以我們這時候應該 -1，把這個太過於遙遠的毒素代謝掉
  • 最後bad變成(2)-1=1
• 從i=7時bad此時是1(1+0)
  • 因為上一個殘留的毒素是1，加上當前i=7是健康的所以+0
  • 我們往前看距離k的位置i=5時，發現當時毒素有+1，但是其實i=5已經距離i=7太遠了！這個毒素的影響性應該要代謝掉
  • 我們只關心前k個值是否有毒素，所以我們這時候應該 -1，把這個太過於遙遠的毒素代謝掉變成(1)-1=0
  • 這時候我們bad==0就可以把nums[i]塞到res裡面。

bad+=1的時機可以寫成這樣(要注意範圍不要變成負的 i>=k)

1
2
3

# i-k+1 看最久遠的病毒，如果是不健康，但是已經過太久，應該代謝掉(-1)
if i >= k and nums[i-k+1] - 1 != nums[i-k]:
    bad -= 1

那我們重新調整一下程式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

def resultsArray(self, nums: List[int], k: int) -> List[int]:
    if k == 1:
        return nums
    bad = 0
    res = []
    # 從 1 開始，因為我們要從第二個數字開始往後比較
    for i in range(1, len(nums)):
        # "增加毒素"的時機：如果當前的值 - 1 不等於前一個值，但表不健康
        if nums[i] - 1 != nums[i - 1]:
            bad += 1
        # "減少毒素"的時機：往回看 nums[i-k+1] 這個值，是否為不健康
        if i >= k and nums[i-k+1] - 1 != nums[i-k]:
            bad -= 1
        if i >= k - 1:
            res.append(nums[i] if bad == 0 else -1)

    return res

還可以更精簡喔，下面是世界選手最簡潔的程式碼：

我們是否可以利用False的特性，直接加在bad上，這樣就不用判斷了！

• True: 代表 0
• False: 代表 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

def resultsArray(self, nums: List[int], k: int) -> List[int]:
    if k == 1:
        return nums
    bad = 0
    res = []
    for i in range(1, len(nums)):
        # 我們透過 False 來判斷是否要增加毒素 +1 
        bad += nums[i] - 1 != nums[i - 1]
        if i >= k:
            # 我們透過 False 來判斷是否要減少毒素 -1
            bad -= nums[i-k+1] - 1 != nums[i-k]
        if i >= k - 1:
            res.append(nums[i] if bad == 0 else -1)

    return res

3 結語

這個題目的解法是我看到別人排名很前面的人寫出來的，因為我還沒刷過sliding window的題目，所以當時完全沒想到這個解法，這次的比賽讓我學到了很多，希望下次可以更好。

4 參考

• Biweekly Contest 137 - Ranking