題目簡(jiǎn)介
進(jìn)入貪心算法環(huán)節(jié)歼秽。
455. 分發(fā)餅干
假設(shè)你是一位很棒的家長(zhǎng)棍潘，想要給你的孩子們一些小餅干且轨。但是详炬，每個(gè)孩子最多只能給一塊餅干。
對(duì)每個(gè)孩子 i，都有一個(gè)胃口值 g[i]痕貌，這是能讓孩子們滿足胃口的餅干的最小尺寸；并且每塊餅干 j糠排，都有一個(gè)尺寸 s[j] 舵稠。如果 s[j] >= g[i]，我們可以將這個(gè)餅干 j 分配給孩子 i 入宦，這個(gè)孩子會(huì)得到滿足哺徊。你的目標(biāo)是盡可能滿足越多數(shù)量的孩子，并輸出這個(gè)最大數(shù)值乾闰。
376. 擺動(dòng)序列
如果連續(xù)數(shù)字之間的差嚴(yán)格地在正數(shù)和負(fù)數(shù)之間交替落追，則數(shù)字序列稱為 擺動(dòng)序列 。第一個(gè)差（如果存在的話）可能是正數(shù)或負(fù)數(shù)涯肩。僅有一個(gè)元素或者含兩個(gè)不等元素的序列也視作擺動(dòng)序列轿钠。
例如巢钓， [1, 7, 4, 9, 2, 5] 是一個(gè) 擺動(dòng)序列 ，因?yàn)椴钪?(6, -3, 5, -7, 3) 是正負(fù)交替出現(xiàn)的疗垛。
相反症汹，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是擺動(dòng)序列，第一個(gè)序列是因?yàn)樗那皟蓚€(gè)差值都是正數(shù)继谚，第二個(gè)序列是因?yàn)樗淖詈笠粋€(gè)差值為零烈菌。
子序列 可以通過(guò)從原始序列中刪除一些（也可以不刪除）元素來(lái)獲得阵幸，剩下的元素保持其原始順序花履。
給你一個(gè)整數(shù)數(shù)組 nums ，返回 nums 中作為 擺動(dòng)序列 的 最長(zhǎng)子序列的長(zhǎng)度 挚赊。
53. 最大子數(shù)組和
給你一個(gè)整數(shù)數(shù)組 nums 诡壁，請(qǐng)你找出一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素），返回其最大和荠割。
子數(shù)組 是數(shù)組中的一個(gè)連續(xù)部分妹卿。
初見(jiàn)思路
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
g.sort()
s.sort()
index = len(s) - 1
result = 0
for i in range(len(g) - 1,-1,-1):
if index >= 0 and s[index] >= g[i]:
result += 1
index -= 1
return result
- 一個(gè)要點(diǎn)，正負(fù)交替的順序不重要蔑鹦，重點(diǎn)是當(dāng)前差值和之前的差值之積一定為負(fù)數(shù)，那么就一定處于正負(fù)交替的過(guò)程中铺纽。還有就是平峰的時(shí)候，不要記入交替的計(jì)數(shù)。（邊界條件：左右邊界、平峰的情況）
class Solution:
def wiggleMaxLength(self, nums: List[int]) -> int:
if len(nums) <= 1:
return len(nums)
pre_diff,cur_diff,result = 0,0,1
for i in range(len(nums)-1):
cur_diff = nums[i+1] - nums[i]
if cur_diff * pre_diff <= 0 and cur_diff != 0:
result += 1
pre_diff = cur_diff
return result
- 使用動(dòng)態(tài)規(guī)劃（貪心）的方法。
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
if len(nums) == 1:
return nums[0]
pre_sum,max_sub_sum = nums[0],nums[0]
for i in range(1,len(nums)):
temp_sum = max(pre_sum + nums[i], nums[i])
max_sub_sum = max(temp_sum, max_sub_sum)
pre_sum = temp_sum
return max_sub_sum
當(dāng)然還有一種更加極限的方法, 當(dāng)且僅當(dāng)前一個(gè)元素為大于0的元素時(shí)加和缘揪，最后結(jié)果數(shù)組中最大值即為我們所求。
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
for i in range(1, len(nums)):
if nums[i-1]>0:
nums[i] += nums[i-1]
return max(nums)
復(fù)盤(pán)思路
https://programmercarl.com/0455.%E5%88%86%E5%8F%91%E9%A5%BC%E5%B9%B2.html
https://programmercarl.com/0376.%E6%91%86%E5%8A%A8%E5%BA%8F%E5%88%97.html
https://programmercarl.com/0053.%E6%9C%80%E5%A4%A7%E5%AD%90%E5%BA%8F%E5%92%8C.html
