簡述

貪心算法是指，在每次作出決策時，只考慮采取當前意義下的最優(yōu)策略。因此，運用貪心算法時要求整體的最優(yōu)可以由局部的最優(yōu)導出。

例題目錄

（目前簡書不支持跳轉(zhuǎn)，各位看官自行下滑吧）

• 1、買賣股票的最佳時機 II
• 2、無重疊區(qū)間
• 3、防曬
• 4、畜欄預定
• 5、雷達設備
• 6、國王游戲
• 7、跳躍游戲
• 8、單調(diào)遞增的數(shù)字

例題

1、買賣股票的最佳時機 II

題目描述：

給定一個數(shù)組，它的第 i 個元素是一支給定股票第 i 天的價格。

設計一個算法來計算你所能獲取的最大利潤。你可以盡可能地完成更多的交易（多次買賣一支股票）。

注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。
示例 1:

輸入: [7,1,5,3,6,4]
輸出: 7

算法

只需要考慮每相鄰兩天的股價，如果當前的股價比前一天的股價高，那就可以加到總利潤里面。

可能有人會問同一天不能同時進行買和賣，如果，按照這種算法，第二天會同時進行買和賣，即會發(fā)生：和，這不符合題意啊。

不要慌，雖然在算法中第二天會同時進行買和賣，其實這兩次交易的總利潤等價于只進行一次交易的利潤，即。因為這是在一段上坡，波峰減去波谷的差值等于把上坡分成多段的差值之和。

代碼

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        for i in range(len(prices) - 1):
            if prices[i+1] > prices[i]:
                profit += (prices[i+1] - prices[i])
        return profit

時間復雜度：O(n)

2、無重疊區(qū)間

題目描述：

給定一個區(qū)間的集合，找到需要移除區(qū)間的最小數(shù)量，使剩余區(qū)間互不重疊。

注意:

可以認為區(qū)間的終點總是大于它的起點。
區(qū)間 [1,2] 和 [2,3] 的邊界相互“接觸”，但沒有相互重疊。

示例 1:

輸入: [ [1,2], [2,3], [3,4], [1,3] ]
輸出: 1

解釋: 移除 [1,3] 后，剩下的區(qū)間沒有重疊。

算法

從起點的貪心算法：

1. 對集合按起點進行排序；
2. 記錄前一個區(qū)間的終點pos，對于當前區(qū)間i，
   如果intervals[i].start >= pos，則：count+=1，pos=intervals[i].end;
   如果intervals[i].start < pos，再分為：
   如果intervals[i].end < pos，則：pos=intervals[i].end
   從終點的貪心算法：
3. 對集合按終點進行排序；
4. 記錄前一個區(qū)間的終點pos，對于當前區(qū)間i，
   如果intervals[i].start >= pos，則：count+=1，pos=intervals[i].end；
   對于從終點的貪心算法，只需要判斷intervals[i].start >= pos的情況，因為已經(jīng)按終點從小到大排好序了，當前的終點一定大于等于pos，所以就少了從起點貪心的第二個“如果”。

因為題目問的是需要移除的最小區(qū)間數(shù)，以上算法的count是最大保留的區(qū)間數(shù)，因此用區(qū)間集合長度減去count就是所求。

代碼

# 從起點貪心
class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        n = len(intervals)
        if n == 0:
            return 0
        intervals.sort(key=lambda x: x[0])
        count = 1
        pos = intervals[0][1]
        for i in range(1, n):
            if intervals[i][0] >= pos:
                pos = intervals[i][1]
                count += 1
            else:
                if intervals[i][1] < pos:
                    pos = intervals[i][1]
        return n - count

# 從終點貪心
class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        n = len(intervals)
        if n == 0:
            return 0
        intervals.sort(key=lambda x: x[1])
        res = 1
        end = intervals[0][1]
        for i in range(1, n):
            if intervals[i][0] >= end:
                end = intervals[i][1]
                res += 1
        return n - res

時間復雜度：
排序+遍歷集合：O(nlogn) + O(n) ≈ O(nlogn)

相似題目

leetcode 435.無重疊區(qū)間

3、防曬

題目描述

有C頭奶牛進行日光浴，第i頭奶牛需要minSPF[i]到maxSPF[i]單位強度之間的陽光。

每頭奶牛在日光浴前必須涂防曬霜，防曬霜有L種，涂上第i種之后，身體接收到的陽光強度就會穩(wěn)定為SPF[i]，第i種防曬霜有cover[i]瓶。

求最多可以滿足多少頭奶牛進行日光浴。

算法

1. 先按minSPF從大到小對奶牛進行排序；
2. 按SPF從大到小對防曬霜進行排序；
3. 遍歷奶牛，選擇可用的SPF值最大的。
   為什么要選擇SPF最大的呢？
   假設當前奶?？蛇x的防曬霜是x和y，并且SPF[x] < SPF[y]，則后面的奶牛只可能出現(xiàn)：“x，y都能用”，“x，y都不能用”，“x能用，y不能用”這三種情況之一。如果我們選擇了y，則對整體的影響比選擇較小的x更好。

代碼

# 讀入數(shù)據(jù)
C, L = map(int, input().split())

min_max_SPF = [[0] * 2 for _ in range(C)]
for i in range(C):
    m1, m2 = map(int, input().split())
    min_max_SPF[i][0],  min_max_SPF[i][1]= m1, m2
    
SPF_cover = [[0] * 2 for _ in range(L)]
for i in range(L):
    s, c = map(int, input().split())
    SPF_cover[i][0], SPF_cover[i][1] = s, c

# 按min從從大到小排序
min_max_SPF.sort(key=lambda x: x[0], reverse=True)
SPF_cover.sort(key=lambda x: x[0], reverse=True)

ans = 0
# 遍歷
for m1, m2 in min_max_SPF:
    for i, tup in enumerate(SPF_cover):
        SPF, cover = tup
        if m1 <= SPF <= m2 and cover > 0:
            SPF_cover[i][1] -= 1
            ans += 1
            break
print(ans)

時間復雜度：O(n^2)
說明：這道題目來自AcWing，數(shù)據(jù)輸入和輸出的方式和leetcode不太一樣。

4、畜欄預定

題目描述

有N頭牛在畜欄中吃草。

每個畜欄在同一時間段只能提供給一頭牛吃草，所以可能會需要多個畜欄。

給定N頭牛和每頭牛開始吃草的時間A以及結(jié)束吃草的時間B，每頭牛在[A,B]這一時間段內(nèi)都會一直吃草。

當兩頭牛的吃草區(qū)間存在交集時（包括端點），這兩頭牛不能被安排在同一個畜欄吃草。

求需要的最小畜欄數(shù)目和每頭牛對應的畜欄方案。

算法

1. 按開始時間對牛進行排序；
2. 維護一個數(shù)組s，記錄當前畜欄最后牛離場的時間；
3. 遍歷每頭牛，在s中尋找一個當前牛的開始時間大于畜欄結(jié)束時間的合適畜欄。若找到了，則把找到的畜欄的結(jié)束時間改成當前牛的；若沒有找到，則在s中添加一個畜欄，記錄當前牛的結(jié)束時間。

代碼

# 讀取數(shù)據(jù)
n = int(input())
cows = [[0] * 3 for _ in range(n)]
for i in range(n):
    cows[i][0], cows[i][1], cows[i][2]= *map(int, input().split()), i

# 按開始時間從小到大排序
cows.sort(key=lambda x: x[0])

s = []
res = [0] * n
for tup in cows:
    start, end, i = tup
    if not s:  # 開始時s為空
        s.append(end)
        res[i] = 0
    else:
        # 遍歷s，尋找一個合適的畜欄
        for j, t in enumerate(s):
            if start > t:
                s[j] = end
                res[i] = j
                break
        else:  # 在已有的畜欄中沒有合適的
            s.append(end)
            res[i] = len(s) - 1

# 打印結(jié)果
print(len(s))
for r in res:
    print(r+1)

時間復雜度：O(n^2)

5、雷達設備

題目描述

假設海岸是一條無限長的直線，陸地位于海岸的一側(cè)，海洋位于另外一側(cè)。

每個小島都位于海洋一側(cè)的某個點上。

雷達裝置均位于海岸線上，且雷達的監(jiān)測范圍為d，當小島與某雷達的距離不超過d時，該小島可以被雷達覆蓋。

我們使用笛卡爾坐標系，定義海岸線為x軸，海的一側(cè)在x軸上方，陸地一側(cè)在x軸下方。

現(xiàn)在給出每個小島的具體坐標以及雷達的檢測范圍，請你求出能夠使所有小島都被雷達覆蓋所需的最小雷達數(shù)目。

算法

1. 計算每個島在x軸上的雷達可選范圍[l[i], r[i]]；
2. 用一個變量pos維護最后一臺雷達的監(jiān)控位置；
3. 遍歷每個島在x軸上的映射，若l[i] > pos，則count+=1，pos=r[i]；否則，pos=min(pos, l[i])

代碼

import math

# 獲取輸入
n, d = map(int, input().split())

islands = [[0] * 2 for _ in range(n)]
for i in range(n):
    islands[i][0], islands[i][1] = map(int, input().split())

def main():
    # 將island的(x, y)轉(zhuǎn)化為x軸上的(l, r)
    for i in range(n):
        x, y = islands[i]
        tmp = d ** 2 - y ** 2
        if tmp < 0:
            return -1
        l, r = x - math.sqrt(tmp), x + math.sqrt(tmp)
        islands[i] = [l, r]
    
    # 按l從小到大排序
    islands.sort(key=lambda x: x[0])
    pos = float('-inf')
    ans = 0
    for l, r in islands:
        if l > pos:
            ans += 1
            pos = r
        else:
            pos = min(pos, r)
    return ans
        
print(main())

時間復雜度：O(n)

相似題目

leetcode 452. 用最少數(shù)量的箭引爆氣球

6、國王游戲

題目描述

恰逢 H 國國慶,國王邀請 n 位大臣來玩一個有獎游戲。

首先,他讓每個大臣在左、右手上面分別寫下一個整數(shù),國王自己也在左、右手上各寫一個整數(shù)。

然后,讓這 n 位大臣排成一排,國王站在隊伍的最前面。

排好隊后,所有的大臣都會獲得國王獎賞的若干金幣,每位大臣獲得的金幣數(shù)分別是:

排在該大臣前面的所有人的左手上的數(shù)的乘積除以他自己右手上的數(shù),然后向下取整得到的結(jié)果。

國王不希望某一個大臣獲得特別多的獎賞,所以他想請你幫他重新安排一下隊伍的順序,使得獲得獎賞最多的大臣,所獲獎賞盡可能的少。

注意,國王的位置始終在隊伍的最前面。

算法

按左右手乘積從小到大的順序排練即為最優(yōu)排列方案。

代碼

# 獲取輸入
n = int(input())
l_k, r_k = map(int, input().split())
array = [[0] * 3 for _ in range(n)]
for i in range(n):
    l, r = map(int, input().split())
    array[i] = [l, r, l * r]
    
array.sort(key=lambda x: x[2])

ans = 0
tmp = l_k
for l, r, _ in array:
    total = tmp // r
    ans = max(ans, total)
    tmp *= l
    
print(ans)

時間復雜度：O(nlogn)

7、跳躍

題目描述

給定一個非負整數(shù)數(shù)組，你最初位于數(shù)組的第一個位置。

數(shù)組中的每個元素代表你在該位置可以跳躍的最大長度。

你的目標是使用最少的跳躍次數(shù)到達數(shù)組的最后一個位置。

示例:

輸入: [2,3,1,1,4]
輸出: 2

說明:

假設你總是可以到達數(shù)組的最后一個位置。

算法

從前往后遍歷nums，用pos和next_pos分別記錄當前步能到達的最大位置和下一步能到達的最大位置。

由于題目保證能達到最后一個位置，因此只用遍歷到倒數(shù)第二個位置。

代碼

class Solution:
    def jump(self, nums: List[int]) -> int:
        step, next_pos, pos = 0, 0, 0
        for i in range(len(nums) - 1):
            next_pos = max(max_pos, nums[i] + i)
            if pos == i:
                step += 1
                pos = max_pos
        return step

時間復雜度：O(n)

題目變化 (LeetCode 55.跳躍游戲)：
給定一個非負整數(shù)數(shù)組，你最初位于數(shù)組的第一個位置。

數(shù)組中的每個元素代表你在該位置可以跳躍的最大長度。

判斷你是否能夠到達最后一個位置。

示例 1:

輸入: [2,3,1,1,4]
輸出: true

算法：
從前往后遍歷 nums，pos 用于記錄能到達的最大位置，
當 i <= pos 時，更新pos到能到達的最大位置；
當 i > pos 時，直接返回 False。

代碼：

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n, pos = len(nums), 0
        for i in range(n):
            if i <= pos:
                pos = max(pos, i + nums[i])
                if pos >= n - 1:
                    return True
            else:
                return False
        return False

時間復雜度：O(n)

8、 單調(diào)遞增的數(shù)字

題目描述

給定一個非負整數(shù) N，找出小于或等于 N 的最大的整數(shù)，同時這個整數(shù)需要滿足其各個位數(shù)上的數(shù)字是單調(diào)遞增。

（當且僅當每個相鄰位數(shù)上的數(shù)字 x 和 y 滿足 x <= y 時，我們稱這個整數(shù)是單調(diào)遞增的。）

示例 1:

輸入: N = 10
輸出: 9

示例 2:

輸入: N = 332
輸出: 299

算法

尋找原數(shù)中非遞增的數(shù)的前一位，若前一位之前有相等的數(shù)，則再往相等數(shù)的第一位，將這位數(shù)減 1，這位數(shù)后面的位數(shù)全部置為 9。由于是從前往后遞增，所以這一位不會是 0。

代碼

class Solution:
    def monotoneIncreasingDigits(self, N: int) -> int:
        """
        尋找原數(shù)組中不滿足遞增的數(shù)的前一位
        """
        arr = list(map(int, list(str(N))))

        index = -1
        for i in range(len(arr) - 1):
            if arr[i] > arr[i+1]:  # 非遞增
                while i > 0:  # 找到相等數(shù)的第一個
                    if arr[i] == arr[i-1]:
                        index = i - 1
                        i -= 1
                    else:
                        break
                if index == -1:
                    index = i
                break

        if index != -1:
            arr[index] -= 1
            for i in range(index+1, len(arr)):
                arr[i] = 9

        return int(''.join(map(str, arr)))

時間復雜度：O(n)