预备知识：贪心法找零钱

思路：** 尽可能多的使用面值大的钞票！**

def recMCOther(coinValueList, change):
    # 该解法前提条件：coinValueList 为整数倍的，从大到小排列！！！
    minCoins = 0
    for coin in coinValueList:
        use = change // coin
        minCoins += use
        change = change - coin * use

    return minCoins

if __name__ == '__main__':
    print(recMCOther([200, 100, 20, 10, 5, 1], 628))

demo1：分糖果 (easy) ---- (排序，贪心)

来源：leetcode 455

类似题目：田忌赛马

思路：while双遍历，想好糖果和孩子什么时候进行转换！！！

# 糖果问题
def findContentChildren(g, s):
    # g: 需求因子列表
    # s: 糖果大小列表
    child, candy = 0, 0
    while child < len(g) and candy < len(s):
        if g[child] < s[candy]:
            child += 1
        candy += 1
    return child

if __name__ == '__main__':
    print(findContentChildren([1, 3, 5, 10], [2, 2, 4, 11]))

demo2：摇摆序列 (medium) ---- (贪心)

来源：leetcode 376

思路：状态机，画图，写状态转换条件

微信图片_20191231122102.png

# 摇摆序列 (leetcode 376)
class Solution(object):
    def wiggleMaxLength(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) < 2:
            return len(nums)

        self.state = 0
        self.max_length = 1

        for i in range(1, len(nums)):
            if self.state == 0:
                self.begin(i, nums)
            elif self.state == 1:
                self.up(i, nums)
            elif self.state == 2:
                self.down(i, nums)            
        return self.max_length
    
    def begin(self, i, nums):
        if nums[i-1] > nums[i]:   # 下降
            self.state = 2
            self.max_length += 1
        elif nums[i-1] < nums[i]: # 上升
            self.state = 1
            self.max_length += 1
    
    def up(self, i, nums):
        if nums[i-1] > nums[i]:   # 下降
            self.state = 2
            self.max_length += 1
    
    def down(self, i, nums):
        if nums[i-1] < nums[i]:   # 上升
            self.state = 1
            self.max_length += 1

demo3: 移出 k 个数字 (medium) ---- (栈，贪心)

来源：leetcode 402

思路：看下图

微信图片_20191231133409.png

class Solution(object):
    def removeKdigits(self, num, k):
        """
        :type num: str
        :type k: int
        :rtype: str
        """
        stack = []
        for i in range(len(num)):
            # 小于栈顶 --> 弹栈后入栈; 否则直接入栈
            while stack != [] and num[i] < stack[-1] and k > 0:
                stack.pop()
                k -= 1
            if num[i] != "0" or stack != []:    # 注意 "0"，双引号不要丢
                stack.append(num[i])
        # k 还有剩余的情况
        while k > 0 and stack != []:
            stack.pop()
            k -= 1
        ans = ''.join(stack)
        return ans if ans else "0"    # 最后可能会栈空，返回 0