今天要來分享幾題和greedy演算法有關的leetcode，然後明天會來分享應用到貪婪策略的演算法（或經典問題）

Leetcode 11. Container With Most Water

題目敘述：給予一個整數的陣列，裡面的整數代表了（柱子）高度，選出兩根柱子能儲存最多容量的水，並返回該容量。

Example:

(圖源：leetcode)

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

分析：會影到容量的因素有兩個：選取柱子的高度和柱子間的距離。我們可以用兩個指標去代表選取的兩根柱子，並且目標是盡量去選擇高的柱子，如果其中一個指標指著的柱子比較矮就要去移動那個指標，因為限制住高度的取決於較矮的柱子，並且這樣才有可能在之後遇到高度比較高的柱子。

class Solution:
    def maxArea(self, height: List[int]) -> int:
        l, r = 0, len(height) - 1
        maxAmount = 0

        while l < r:
            if height[r] >= height[l]:
                maxAmount = max(maxAmount, (r - l) * height[l])
                l += 1
            else:
                maxAmount = max(maxAmount, (r - l) * height[r])
                r -= 1
        
        return maxAmount

Leetcode 763. Partition Labels

題目敘述：有一個input的字串，我們的目標是盡可能地去分割它成好幾個子字串，但是分割是需要去依循規則的：我們需要讓每個字元只出現其中一個子字串中，而不會出現在其他子字串，例如："A"只會出現在第二個子字串，不會出現在其他分割出來的子字串。回傳所有分割出來的子字串的長度。

Example:

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.

分析：我們要盡可能地去找出出現在字串中的每一個獨立的字元會出現在字串中的最遠index，例如：上面的example字串的"a"最遠的index為8，我們可以利用hash map紀錄。當我們開始分割時，我們會去依序拜訪字串中的每個字元，並且讓這些字元中最遠的index當作「分割點」，當被拜訪的字元追上分割點時即完成一次分割。

以Python實作

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        table = {}
        for i in range(len(s)):
            table[s[i]] = i
        
        res = []
        size, end = 0, 0
        for i in range(len(s)):
            size += 1
            end = max(end, table[s[i]])
            if i == end:
                res.append(size)
                size = 0
        
        return res

Leetcode 134. Gas Station

本題是今天最後一題，很像益智問答的題目，蠻有趣的但比較不直覺＾＾

題目敘述：想像我們要去聖地巡迴，每個聖地都有一個加油站，可以加gas[i]公升的油，而每次從某個聖地出發都會消耗cost[i]公升的油，我們應該從哪一站出發才能成功的巡迴聖地回到最初的出發點。（保證所有測資都只會有一個答案）

Example:

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.

分析：首先有個大前提，那就是可以加的油量要大於等於消耗的油量。如果符合這個大前提，我們去計算出每個聖地加的油量和消耗得油量的差距並形成一個陣列，接著我們要去找出陣列中某段總和為正的並且可以一路延伸到最後一個值的subarray的第一個index，因為題目保證只有一個答案，所以這個index就是我們的答案。而利用兩個指標一個指著subarray的起點和終點，我們在之前動態規劃的章節也有提到類似的概念（maximum subarray），但是也可以greedy的方式來解釋：我們每一次都盡量讓我們的右指標向後拓展，但是當某個index的value會因為和前面的總和相加變小的話就捨棄前面的subarray，重新計算。

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        if sum(gas) < sum(cost):
            return -1
        diff = [g - c for g, c in zip(gas, cost)]
        curMax = diff[0]

        l, r = 0, 1
        while r < len(diff):
            if curMax + diff[r] <= diff[r]:
                l = r
                curMax = diff[r]
            else:
                curMax += diff[r]

            r += 1
 
        return l

沒有庫存真的痛苦☠︎