最後更新日期: 14/12/2024

Table of Contents:

📄Summary

🚨Why It Matters

效率優良：可對最優化問題快速找到答案，因其僅需選擇當前最佳方案
適用問題：最小生成樹（Minimum Spanning Tree）、背包（Knapsack）和活動選擇（Activity Selection）問題等
應用廣泛：調度（Scheduling）、路徑規劃（Path Planning）和財務管理（Financial Management）等問題都以此為基礎

🗺️The Big Picture

DA101: Greedy Algorithm（貪婪演算法）

😐45. Jump Game II

Description

　　給予一個整數陣列nums，我們從首個索引（0-indexed）開始。nums[i]表在i點時可再往前的最大步。現在已知能跳到末個索引，請回傳過程跳躍的最小步數。

Example 1:

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [2,3,0,1,4]
Output: 2

Solutions

⭐Approach #1: Greedy

　　前題是判斷能否從起點到終點，此題則是告知必然可以，求出最小跳躍次數。我們應用貪婪精神，在每次的能到範圍中，找尋能到更遠的最大值：

用兩指標l和r決定遍歷範圍
用res紀錄要跳次數
當r未達末索引時：
- 用maxJump記錄跳過res步後，所能到的最遠處
- 在l與r間找尋最遠處
- 確認最遠處後：
  - 將l移到下個區間的左邊界（r+1），因為必然能到終點
  - 將r移到最遠處，成為下個區間的右邊界
  - res+1
遍歷結束後，res即為所求

　　這樣的時間複雜度為O(n)，空間複雜度為O(1)。

class Solution:
    def jump(self, nums: List[int]) -> int:
        l, r = 0, 0
        res = 0
        while r < (len(nums) - 1):
            maxJump = 0
            for i in range(l, r + 1):
                maxJump = max(maxJump, i + nums[i])
            l = r + 1
            r = maxJump
            res += 1
        return res

😐53. Maximum Subarray

Description

　　給予一個整數陣列nums，找出元素和為最大的子陣列（subarray），並回傳此和。

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Example 2:

Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

Solutions

Approach #1: Optimized Brute Force

　　若用暴力法，時間複雜度為O(n²)，空間複雜度為O(1)。

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_subarray = -math.inf
        for i in range(len(nums)):
            current_subarray = 0
            for j in range(i, len(nums)):
                current_subarray += nums[j]
                max_subarray = max(max_subarray, current_subarray)

        return max_subarray

⭐Approach #2: Greedy

　　此題適合用貪婪演算法來處理，我們選擇子陣列的開頭時，可以：

拋掉總和<0
選擇和最大的

　　因此：

用res當回傳結果，並先設陣列首個元素nums[0]
用total紀錄子陣列和
遍歷nums：
- 將元素加到total中，與res比較大小，留住最大值
- 當total<0，代表包含前面元素已不會是答案，可捨去重新開始（將total設為0）

　　這樣的時間複雜度為O(n)，空間複雜度為O(1)。

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        res = nums[0]

        total = 0
        for n in nums:
            total += n
            res = max(res, total)
            if total < 0:
                total = 0
        return res

😐55. Jump Game

Description

　　給予一個整數陣列nums，請從首個索引往前。nums[i]代表經過i點時可再往前的最大步數。若最後能到達末個索引，回傳true，否則回傳false。

Example 1:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

Solutions

Approach #1: Backtracking

　　找出所有可能的時間複雜度為O(2ⁿ)，空間複雜度為O(n)。

class Solution:
    def canJumpFromPosition(self, position: int, nums: List[int]) -> bool:
        if position == len(nums) - 1:
            return True

        furthestJump = min(position + nums[position], len(nums) - 1)
        for nextPosition in range(position + 1, furthestJump + 1):
            if self.canJumpFromPosition(nextPosition, nums):
                return True

        return False

    def canJump(self, nums: List[int]) -> bool:
        return self.canJumpFromPosition(0, nums)

⭐Approach #2: Greedy

　　若用動態規劃（紀錄先前結果），時間複雜度能降為O(n²)。而反過來看待問題，則可以應用貪婪演算法來優化：

用goal代表能否從此點跳至終點，預設為末項索引值
從倒數第二個元素往回遍歷：
- 其值若能到達goal，則更新goal為其索引（最終能成，就該能到與其連結的中間站）
- 不能到達，則忽略此元素
遍歷完後，若goal為0，就代表可行

　　這樣的時間複雜度為O(n)，空間複雜度為O(1)。

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        goal = len(nums) - 1

        for i in range(len(nums) - 2, -1, -1):
            if i + nums[i] >= goal:
                goal = i
        return goal == 0

😐134. Gas Station

Description

　　在條環狀路上有n家瓦斯站，陣列gas記錄每家存放瓦斯量。現在有台可存放無限瓦斯的坦克，陣列cost紀載它從第i跑到i+1站所消耗的瓦斯。請告知從第幾個站出發，能順時針地成功跑一圈。不可能請回傳-1，若有解則會是唯一解。

Example 1:

Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.

Example 2:

Input: gas = [2,3,4], cost = [3,4,3]
Output: -1
Explanation:
You can't start at station 0 or 1, as there is not enough gas to travel to the next station.
Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can't travel around the circuit once no matter where you start.

Solutions

Approach #0: Brute Force

　　若直接嘗試從各站出發，看能否到達終點。這樣的時間複雜度為O(n²)，必然得再考慮其他作法，但也有兩個心得：

無法繼續往前的情況：sum(gas) < sum(cost)
連開始都無法的情況：gas[i] - cost[i] < 0

⭐Approach #1: One pass

　　我們從前面的暴力解得知，要當起點start的最低條件，是gas[start] - cost[start]需>0。我們從後往前回推，若起點與終點最終能相會就代表可從相會點出發：

以start作為末端元素往前判斷，誰至少能當起點
若total有餘，則將終點end往後，加上其損耗
當total<0時則再將start往前，嘗試讓total≥0，得以往後移動end
持續往內夾擊，直到兩點相交：
- 若相交時total≥0，代表以start為起點可行
- 不然則回傳-1，因已嘗試過所有可能

　　這樣的時間複雜度為O(n)，空間複雜度為O(1)。

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        start, end = len(gas) - 1, 0
        total = gas[start] - cost[start]

        while start >= end:
            while total < 0 and start >= end:
                start -= 1
                total += gas[start] - cost[start]
            if start == end:
                return start
            total += gas[end] - cost[end]
            end += 1
        return -1

😐406. Queue Reconstruction by Height

Description

　　給予一個陣列people，代表一群人在Queue中的資料。people[i] = [h_i, k_i]代表第i個人的身高和有多少人≥此身高。請重排此people，讓資料中的k符合情況。

Example 1:

Input: people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
Output: [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
Explanation:
Person 0 has height 5 with no other people taller or the same height in front.
Person 1 has height 7 with no other people taller or the same height in front.
Person 2 has height 5 with two persons taller or the same height in front, which is person 0 and 1.
Person 3 has height 6 with one person taller or the same height in front, which is person 1.
Person 4 has height 4 with four people taller or the same height in front, which are people 0, 1, 2, and 3.
Person 5 has height 7 with one person taller or the same height in front, which is person 1.
Hence [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] is the reconstructed queue.

Example 2:

Input: people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
Output: [[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

Solutions

⭐Approach #1: Greedy

　　這題適合用貪婪觀念來處理：

先以身高從高到低排序人
以前面該有多少人為索引依據來插入元素（較高者即能放在對的位置，即便被較矮的人擠到後面，也會因為他們較矮而可接受）

　　這樣的時間複雜度為O(N²)，空間複雜度為O(N)。

from typing import List


class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people.sort(key=lambda x: (-x[0], x[1]))
        output = []
        for p in people:
            output.insert(p[1], p)
        return output

😐581. Shortest Unsorted Continuous Subarray

Description

　　給予一個整數陣列nums，其中會有幾處不符升序（ascending）排列。找出該被一起排序的最小範圍（子陣列）並回傳此範圍的長度。

Example 1:

Input: nums = [2,6,4,8,10,9,15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.

Example 2:

Input: nums = [1,2,3,4]
Output: 0

Example 3:

Input: nums = [1]
Output: 0

Solutions

❌Approach #1: Brute Force

　　若用最直觀的暴力解，時間複雜度為O(n³)，空間複雜度為O(1)。

def findUnsortedSubarray(nums):
    res = len(nums)
    for i in range(len(nums)):
        for j in range(i, len(nums) + 1):
            min_val = float('inf')
            max_val = float('-inf')
            prev = float('-inf')
            for k in range(i, j):
                min_val = min(min_val, nums[k])
                max_val = max(max_val, nums[k])
            if (i > 0 and nums[i - 1] > min_val) or (j < len(nums) and nums[j] < max_val):
                continue
            k = 0
            while k < i and prev <= nums[k]:
                prev = nums[k]
                k += 1
            if k != i:
                continue
            k = j
            while k < len(nums) and prev <= nums[k]:
                prev = nums[k]
                k += 1
            if k == len(nums):
                res = min(res, j - i)
    return res

　　若用優化過的暴力解，時間複雜度為O(n²)，空間複雜度為O(1)。

def findUnsortedSubarray(nums):
    l = len(nums)
    r = 0
    for i in range(len(nums) - 1):
        for j in range(i + 1, len(nums)):
            if nums[j] < nums[i]:
                r = max(r, j)
                l = min(l, i)
    return 0 if r - l < 0 else r - l + 1

Approach #2: Sort

　　我們也可以用排序來幫助處理：

建立一個備份陣列snums並排序它
用start和end記錄需重排序（元素與有序陣列中的元素不一致）的起點和終點
用同個索引值遍歷兩陣列，當有元素不相等時，用其更新start和max
若start和end總長>0，回傳它；不然則回傳0

　　這樣的時間複雜度為O(nlogn)，空間複雜度為O(n)。

class Solution:
    def findUnsortedSubarray(self, nums):
        snums = nums.copy()
        snums.sort()
        start = len(snums)
        end = 0
        for i in range(len(snums)):
            if snums[i] != nums[i]:
                start = min(start, i)
                end = max(end, i)

        res = end - start + 1
        if res > 0:
            return res
        else:
            return 0

⭐Approach #3: Using Stack

　　我們可以使用堆疊stack：

遍歷nums，依序放元素進stack
- 數值不升反降時：持續取出堆疊元素，用其更新l，直到頂部元素≤它
- 遍歷完後，就能確定目標子陣列的最左邊界
清空堆疊，從右往左地遍歷nums來找到右邊界
最後結果（r-l+1）若>0則回傳，否則則回傳0（代表沒有需要排序的子陣列）

　　這樣子的時間複雜度則再降到O(n)，空間複雜度仍為O(n)。

class Solution:
    def findUnsortedSubarray(self, nums):
        stack = []
        # 找尋需重排範圍的左邊界
        l = len(nums)
        for i in range(len(nums)):
            # 遇到有比前面小的數字
            while stack and nums[stack[-1]] > nums[i]:
                l = min(l, stack.pop())
            stack.append(i)
        stack.clear()
        # 找尋需重排範圍的右邊界
        r = 0
        for i in range(len(nums) - 1, -1, -1):
            # 遇到有比前面大的數字
            while len(stack) != 0 and nums[stack[-1]] < nums[i]:
                r = max(r, stack.pop())
            stack.append(i)
        res = r - l + 1
        return max(res, 0)

⭐Approach #4: Without Using Extra Space

　　空間複雜度能再優化，因只需在過程中儲存子陣列的左右邊界。因此我們：

從左至右遍歷陣列，將左邊界設為首個值降處
從右至左遍歷陣列，將右邊界設為首個值升處
找出子陣列當中的最小值和最大值
以最小值做判斷，左移左邊界直到有值比它小為止，確立了最終左邊界
以最大值做判斷，右移右邊界直到有值比它大為止，確立了最終右邊界

　　這樣子的時間複雜度為O(n)，空間複雜度為O(1)。

from typing import List


class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return 0
        l = 0
        # 將l停在首個不遞增處
        while l < len(nums) - 1 and nums[l] <= nums[l + 1]:
            l += 1
        r = len(nums) - 1
        # 將r停在首個不遞減處
        while r > 0 and nums[r] >= nums[r - 1]:
            r -= 1
        # 代表整體已有序
        if l >= r:
            return 0

        # 延伸左邊界，確保無序區間內的最小值大於等於左邊界
        while l > 0 and min(nums[l:r + 1]) < nums[l - 1]:
            l -= 1
        # 延伸右邊界，確保無序區間內的最大值小於等於右邊界
        while r < len(nums) - 1 and max(nums[l:r + 1]) > nums[r + 1]:
            r += 1

        return r - l + 1

😐621. Task Scheduler

Description

　　給予一個字元陣列tasks（皆為大寫英文字母），代表CPU要做的工作集合。可任意決定工作（字元）順序，所需時間皆同，CPU也能保持閒置狀態（idle）。

　　然而，同種工作再次被完成前，CPU至少需要非負整數n個單位時間來冷卻。請回傳CPU要完成tasks所需最少單位時間。

Example 1:

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: 
A -> B -> idle -> A -> B -> idle -> A -> B
There is at least 2 units of time between any two same tasks.

Example 2:

Input: tasks = ["A","A","A","B","B","B"], n = 0
Output: 6
Explanation: On this case any permutation of size 6 would work since n = 0.
["A","A","A","B","B","B"]
["A","B","A","B","A","B"]
["B","B","B","A","A","A"]
...
And so on.

Example 3:

Input: tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
Output: 16
Explanation: 
One possible solution is
A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> idle -> idle -> A -> idle -> idle -> A

Solutions

⭐Approach #1: Greedy

　　要盡快完成工作，那原則是讓出現頻率最高者相隔最遠，也就是貪婪演算法的精神。因此我們：

統計tasks中的任務出現次數，並排序成為frequencies
將閒置使間idle_time先設為最大值
持續拿出frequencies中頻率最高者並平均擺放，確認最少idle_time所需
元素皆拿出後，max(0, idle_time)+ len(tasks)即為所求

　　這樣的時間複雜度為O(N_total)（N_total為任務種類數，故為常數時間），空間複雜度則為O(1)。

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        frequencies = [0] * 26
        for t in tasks:
            frequencies[ord(t) - ord('A')] += 1

        frequencies.sort()

        # max frequency
        f_max = frequencies.pop()
        idle_time = (f_max - 1) * n

        while frequencies and idle_time > 0:
            idle_time -= min(f_max - 1, frequencies.pop())
        idle_time = max(0, idle_time)

        return idle_time + len(tasks)

⭐Approach #2: Math

　　我們也可以直接求總時數：

統計出各任務的出現次數，找出：
- 任務出現的最高頻率
- 多少任務具備此頻率
回傳max(len(tasks), (f_max - 1) * (n + 1) + n_max)：
- 前者：此情況CPU不需閒置時間來冷卻
- 後者：（f_max - 1）次數＊（n + 1）組＋（n_max）具備最高頻率的任務數

　　這樣的時間複雜度為O(N_total)（N_total為任務種類數，故為常數時間），空間複雜度則為O(1)。

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        frequencies = [0] * 26
        for t in tasks:
            frequencies[ord(t) - ord('A')] += 1

        f_max = max(frequencies)
        n_max = frequencies.count(f_max)

        return max(len(tasks), (f_max - 1) * (n + 1) + n_max)

😐678. Valid Parenthesis String

Description

　　給予一個字串s，裡面只有三種字元（左括號(、右括號)、和星號 *）組合，請判斷s是否合法（valid），規則如下：

任何(並得配對一個)，反之亦然
所配對的(必得在)前面
*可被視為(、)，或是""

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "(*)"
Output: true

Example 3:

Input: s = "(*))"
Output: true

Solutions

❌Approach #1: Brute Force

　　直觀的暴力解，會是持續擴大範圍判斷字串是否有效。

　　這樣的時間複雜度為O(N*3^N)，空間複雜度為O(N)。

Approach #2: Dynamic Programming

　　前面的暴力解會造成超時，但若暫存過往的判斷結果，就可以加以提升。

　　這樣的的時間複雜度為O(N³)，空間複雜度則為O(N²)。

class Solution:
    def checkValidString(self, s: str) -> bool:
        # key=(i, leftCount) -> isValid
        dp = {(len(s), 0): True}

        def dfs(i, left):
            if left < 0:
                return False
            if i == len(s):
                return left == 0
            if (i, left) in dp:
                return dp[(i, left)]

            if s[i] == "(":
                dp[(i, left)] = dfs(i + 1, left + 1)
            elif s[i] == ")":
                dp[(i, left)] = dfs(i + 1, left - 1)
            else:
                dp[(i, left)] = (
                        dfs(i + 1, left + 1) or
                        dfs(i + 1, left - 1) or
                        dfs(i + 1, left)
                )
            return dp[(i, left)]

        return dfs(0, 0)

⭐Approach #3: Greedy

　　因為出現元素有可成為(、)，或是""的*，所以判斷重點不再是合法性，而是平衡性。只要此情況的平衡性可達0（最小值），那就能成為有效括號組合。因此我們用lo和hi代表處理當前字元後(可能呈現數量的最小和最大值，只要遍歷結束時lo為0那即可回傳True。

遇到的是(則將lo += 1，否則-=1
遇到的是)則將hi -= 1，否則+=1
過程hi若已<0，代表已有太多)，必然為非法情況
過程中lo若<0則將其歸0，因hi>0，合法可能性仍存在
最後判斷lo == 0，即為所求

　　這樣的時間複雜度為O(N)，空間複雜度為O(1)。

class Solution(object):
    def checkValidString(self, s):
        lo, hi = 0, 0
        for c in s:
            if c == '(':
                lo += 1
            else:
                lo -= 1
            if c == ')':
                hi -= 1
            else:
                hi += 1
            # too many ')' so must be invalid
            if hi < 0:
                return False
            lo = max(lo, 0)

        return lo == 0

😐763. Partition Labels

Description

　　給予一個字串s，請嘗試切分它成不同子字串，使得每個字母（letter）都只集中出現在單一子字串中。請回傳切分完各子字串的長度陣列。

Example 1:

Input: s = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation:
The partition is "ababcbaca", "defegde", "hijhklij".
This is a partition so that each letter appears in at most one part.
A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits s into less parts.

Example 2:

Input: s = "eccbbbbdec"
Output: [10]

Solutions

⭐Approach #1: Greedy

　　此題要求分切後，同字母不該出現在不同區間中。因此：

先遍歷一次字串，記錄各字母最後出現的位置
再遍歷一次字串，比對當前元素與最後出現的位置，將中間包成一區間
將各區間長度加到res中，遍歷完後res即為所求。

　　這樣的時間複雜度為O(N)，空間複雜度為O(1)。

class Solution:
    def partitionLabels(self, S: str) -> List[int]:
        lastIndex = {}
        # count the last index of each char
        for i, v in enumerate(S):
            lastIndex[v] = i

        intervalLen = 0
        goal = 0
        res = []
        for i, v in enumerate(S):
            goal = max(goal, lastIndex[v])
            intervalLen += 1

            # if the current index is the goal, then we have a partition
            if goal == i:
                res.append(intervalLen)
                intervalLen = 0
        return res

😐846. Hand of Straights

Description

　　Alice有副手牌hand，現在想調整其順序，讓它們分成不同組（group），各組數量等同groupSize且也連續。若可行請回傳True，否則回傳False。

Example 1:

Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
Output: true
Explanation: Alice's hand can be rearranged as [1,2,3],[2,3,4],[6,7,8]

Example 2:

Input: hand = [1,2,3,4,5], groupSize = 4
Output: false
Explanation: Alice's hand can not be rearranged into groups of 4.

Solutions

⭐Approach #1: Greedy with Heap

　　要湊成連續手牌，我們可以從手牌中最小值開始：

用count統計數值出現頻率
將數值以最小堆積minH來存放
當minH仍有值時，持續以最小值當頭來組成手牌，並更新count
若能順利清空minH，則回傳True

　　這樣的時間複雜度為O(NlogN)，空間複雜度為O(N)。

class Solution:
    def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
        if len(hand) % groupSize:
            return False

        count = defaultdict(int)
        for n in hand:
            count[n] += 1

        minH = list(count.keys())
        heapq.heapify(minH)
        while minH:
            first = minH[0]
            for i in range(first, first + groupSize):
                if i not in count:
                    return False
                count[i] -= 1
                if count[i] == 0:
                    # the next round would fail
                    if i != minH[0]:
                        return False
                    heapq.heappop(minH)
        return True

😐918. Maximum Sum Circular Subarray

Description

　　給予一個大小為n的循環整數陣列nums，請回傳一個非空子陣列的最大和。

Example 1:

Input: nums = [1,-2,3,-2]
Output: 3
Explanation: Subarray [3] has maximum sum 3.

Example 2:

Input: nums = [5,-3,5]
Output: 10
Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10.

Example 3:

Input: nums = [-3,-2,-3]
Output: -2
Explanation: Subarray [-2] has maximum sum -2.

Solutions

Approach #1: Enumerate prefix and suffix sums

　　我們可以直觀地分成有環和無環來考慮：

遍歷一次陣列，用rightMax記錄位置I的右邊子陣列最大和
再遍歷一次陣列：
- 記錄無環狀況的最大值maxSum
- 藉由rightMax，算出有環狀況的最大值specialSum
最後比較無環狀況和有環狀況的最大和，即為所求

　　這樣的時間與空間複雜度皆為O(N)。

class Solution:
    def maxSubarraySumCircular(self, nums):
        rightMax = [0] * len(nums)

        # 位置i儲存其右側的最大子陣列和
        rightMax[len(nums) - 1] = nums[len(nums) - 1]
        suffixSum = nums[len(nums) - 1]
        for i in range(len(nums) - 2, -1, -1):
            suffixSum += nums[i]
            rightMax[i] = max(rightMax[i + 1], suffixSum)

        # 跨越兩端的子陣列和
        specialSum = nums[0]
        prefixSum = 0
        curMax = 0
        maxSum = nums[0]
        for i in range(len(nums)):
            curMax = max(curMax, 0) + nums[i]
            # Kadane's algorithm
            maxSum = max(maxSum, curMax)

            prefixSum += nums[i]
            if i < len(nums) - 1:
                specialSum = max(specialSum, prefixSum + rightMax[i + 1])

        return max(maxSum, specialSum)

⭐Approach #2: Calculate the “Minimum Subarray”

　　我們可以藉由整體和扣除最小子陣列和來考慮環狀串列的特性：

遍歷陣列：用currentSubArrayMaxSum和currentSubArrayMinSum來完成allSubArrayMaxSum和allSubArrayMinSum
遍歷完後，若整體和==子陣列最小和：
- 所有數字皆為負，即可回傳allSubArrayMaxSum
- 否則回傳max(allSubArrayMaxSum, _sum - allSubArrayMinSum)，考慮環狀情況

　　這樣的時間複雜度為O(N)，空間複雜度為O(1)。

class Solution:
    def maxSubarraySumCircular(self, nums):
        currentSubArrayMaxSum = 0
        currentSubArrayMinSum = 0
        _sum = 0
        allSubArrayMaxSum = nums[0]
        allSubArrayMinSum = nums[0]

        for num in nums:
            # 用0代表放棄前面的子陣列
            currentSubArrayMaxSum = max(currentSubArrayMaxSum, 0) + num
            allSubArrayMaxSum = max(allSubArrayMaxSum, currentSubArrayMaxSum)

            # 用0代表放棄前面的子陣列
            currentSubArrayMinSum = min(currentSubArrayMinSum, 0) + num
            allSubArrayMinSum = min(allSubArrayMinSum, currentSubArrayMinSum)

            _sum += num

        # 代表所有數字都是負數
        if _sum == allSubArrayMinSum:
            return allSubArrayMaxSum
        else:
            return max(allSubArrayMaxSum, _sum - allSubArrayMinSum)

😐978. Longest Turbulent Subarray

Description

　　給予一個整數陣列arr，請回傳處於洶湧（turbulent）狀態的子陣列最大長度。

Example 1:

Input: arr = [9,4,2,10,7,8,8,1,9]
Output: 5
Explanation: arr[1] > arr[2] < arr[3] > arr[4] < arr[5]

Example 2:

Input: arr = [4,8,12,16]
Output: 2

Example 3:

Input: arr = [100]
Output: 1

Solutions

⭐Approach #1: Greedy( Sliding Window )

　　陣列元素要維持洶湧狀態，其前兩個元素的大小關係得不相等，且與此兩元素的大小相異（>或<）。我們可用貪婪精神搭配移動視窗來處理：

用l和r做為窗口邊界，持續移動r來遍歷陣列arr
用res紀錄洶湧子陣列最大長，其不管如何最小值為1
用prev紀錄前兩元素的大小關係，幫助判斷當前兩元素關係的延伸趨勢
遍歷陣列
- 若當前趨勢與前個趨勢相異，則更新res
- 若趨勢停止變化則收緊窗口，找尋下波趨勢
遍歷完後，res即為所求

　　這樣的時間複雜度為O(N)，空間複雜度為O(1)。

from typing import List


class Solution:
    def maxTurbulenceSize(self, arr: List[int]) -> int:
        l, r = 0, 1
        res = 1
        # 前個趨勢
        prev = ""

        # 用r遍歷陣列
        while r <= len(arr) - 1:
            # 趨勢向下且與前個趨勢相異
            if arr[r - 1] > arr[r] and prev != ">":
                res = max(res, r - l + 1)
                r += 1
                prev = ">"
            # 趨勢向上且與前個趨勢相異
            elif arr[r - 1] < arr[r] and prev != "<":
                res = max(res, r - l + 1)
                r += 1
                prev = "<"
            # 趨勢停止變化，收緊窗口
            else:
                # 值相等，右移窗口右邊界
                if arr[r] == arr[r - 1]:
                    r = r + 1
                l = r - 1
                prev = ""
        return res

😐1605. Find Valid Matrix Given Row and Column Sums

Description

　　給予兩個非負整數陣列rowSum和colSum，其中rowSum[i]存放一個二維陣列第i列的和，colSum[j]存放第j行的和。我們不知道原二維陣列確切內容，但可從這兩陣列知道相關資訊。

　　請回傳一個符合此條件的任意二維陣列，這必然會有答案。

Example 1:

Input: rowSum = [3,8], colSum = [4,7]
Output: [[3,0], [1,7]]
Explanation: 
0th row: 3 + 0 = 3 == rowSum[0]
1st row: 1 + 7 = 8 == rowSum[1]
0th column: 3 + 1 = 4 == colSum[0]
1st column: 0 + 7 = 7 == colSum[1]
The row and column sums match, and all matrix elements are non-negative.
Another possible matrix is: [[1,2], [3,5]]

Example 2:

Input: rowSum = [5,7,10], colSum = [8,6,8]
Output: [[0,5,0], [6,1,0], [2,0,8]]

Solutions

⭐Approach #1: Greedy

　　我們要重組此陣列，可用貪婪概念（做當下的最好決策）來完成：從滿足此行和與此列和中取較小者為元素，這在確保會有陣列滿足條件時為可行。

　　這樣的時間複雜度為O(N x M)，空間複雜度為O(N + M)。

class Solution:
    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:
        N = len(rowSum)
        M = len(colSum)

        currRowSum = [0] * N
        currColSum = [0] * M

        result = [[0] * M for _ in range(N)]
        for i in range(N):
            for j in range(M):
                result[i][j] = min(rowSum[i] - currRowSum[i], colSum[j] - currColSum[j])

                currRowSum[i] += result[i][j]
                currColSum[j] += result[i][j]

        return result

⭐Approach #2: Space Optimized Greedy

　　與解法1相同，但優化了所需暫存空間。

　　這樣的時間複雜度為O(N x M)，空間複雜度為O(1)。

class Solution:
    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:
        N = len(rowSum)
        M = len(colSum)

        result = [[0] * M for _ in range(N)]
        for i in range(N):
            for j in range(M):
                result[i][j] = min(rowSum[i], colSum[j])

                rowSum[i] -= result[i][j]
                colSum[j] -= result[i][j]

        return result

😐1871. Jump Game VII

Description

　　給予一個0-indexed的二元字串s，和兩整數minJump 和maxJump 。一開始你在起點0，要到達字串尾端。中間移動（從索

引i到j）的規則為：

i + minJump <= j <= min(i + maxJump, s.length - 1)
s[j] == '0'

Example 1:

Input: s = "011010", minJump = 2, maxJump = 3
Output: true
Explanation:
In the first step, move from index 0 to index 3. 
In the second step, move from index 3 to index 5.

Example 2:

Input: s = "01101110", minJump = 2, maxJump = 3
Output: false

Solutions

😐1899. Merge Triplets to Form Target Triplet

Description

　　給予一個二維陣列triplets，每個單位存放三元素（triplets[i] = [a_i, b_i, c_i]），和一個整數陣列target = [x, y, z]。現在想從triplets找到完成target的組合，規則是從triplets選出兩個triplet比大小，留下較大元素成為新的triplet。若能在執行數次後得到等同target的triplet則回傳True，否則回傳False。

Example 1:

Input: triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5]
Output: true
Explanation: Perform the following operations:
- Choose the first and last triplets [[2,5,3],[1,8,4],[1,7,5]]. Update the last triplet to be [max(2,1), max(5,7), max(3,5)] = [2,7,5]. triplets = [[2,5,3],[1,8,4],[2,7,5]]
The target triplet [2,7,5] is now an element of triplets.

Example 2:

Input: triplets = [[3,4,5],[4,5,6]], target = [3,2,5]
Output: false
Explanation: It is impossible to have [3,2,5] as an element because there is no 2 in any of the triplets.

Example 3:

Input: triplets = [[2,5,3],[2,3,4],[1,2,5],[5,2,3]], target = [5,5,5]
Output: true
Explanation: Perform the following operations:
- Choose the first and third triplets [[2,5,3],[2,3,4],[1,2,5],[5,2,3]]. Update the third triplet to be [max(2,1), max(5,2), max(3,5)] = [2,5,5]. triplets = [[2,5,3],[2,3,4],[2,5,5],[5,2,3]].
- Choose the third and fourth triplets [[2,5,3],[2,3,4],[2,5,5],[5,2,3]]. Update the fourth triplet to be [max(2,5), max(5,2), max(5,3)] = [5,5,5]. triplets = [[2,5,3],[2,3,4],[2,5,5],[5,5,5]].
The target triplet [5,5,5] is now an element of triplets.

Solutions

⭐Approach #1: Greedy

　　此題關鍵在於適合的triplet，其元素不該比target內的對應元素還大。因此：

使用雜湊表good紀錄是否三位置皆有適合元素出現。
遍歷triplets，若t中任一元素比target的對應元素大，那絕對不合適
檢查符合條件的t，看其三元素是否有符合target的
遍歷完triplets時，若good長度為3則代表可滿足題目要求

　　這樣的時間與空間複雜度皆為O(N)。

class Solution:
    def mergeTriplets(self, triplets: List[List[int]], target: List[int]) -> bool:
        good = set()

        for t in triplets:
            if t[0] > target[0] or t[1] > target[1] or t[2] > target[2]:
                continue
            for i, v in enumerate(t):
                if v == target[i]:
                    good.add(i)
        return len(good) == 3

🧰: LeetCode – Greedy

📄Summary

🚨Why It Matters

🗺️The Big Picture

😐45. Jump Game II

Description

Example 1:

Example 2:

Solutions

⭐Approach #1: Greedy

😐53. Maximum Subarray

Description

Example 1:

Example 2:

Example 3:

Solutions

Approach #1: Optimized Brute Force

⭐Approach #2: Greedy

😐55. Jump Game

Description

Example 1:

Example 2:

Solutions

Approach #1: Backtracking

⭐Approach #2: Greedy

😐134. Gas Station

Description

Example 1:

Example 2:

Solutions

Approach #0: Brute Force

⭐Approach #1: One pass

😐406. Queue Reconstruction by Height

Description

Example 1:

Example 2:

Solutions

⭐Approach #1: Greedy

😐581. Shortest Unsorted Continuous Subarray

Description

Example 1:

Example 2:

Example 3:

Solutions

❌Approach #1: Brute Force

Approach #2: Sort

⭐Approach #3: Using Stack

⭐Approach #4: Without Using Extra Space

😐621. Task Scheduler

Description

Example 1:

Example 2:

Example 3:

Solutions

⭐Approach #1: Greedy

⭐Approach #2: Math

😐678. Valid Parenthesis String

Description

Example 1:

Example 2:

Example 3:

Solutions

❌Approach #1: Brute Force

Approach #2: Dynamic Programming

⭐Approach #3: Greedy

😐763. Partition Labels

Description

Example 1:

Example 2:

Solutions

⭐Approach #1: Greedy

😐846. Hand of Straights

Description

Example 1:

Example 2:

Solutions

⭐Approach #1: Greedy with Heap

😐918. Maximum Sum Circular Subarray

Description

Example 1: