贪心

方法一贪心

一开始我们没有钱，顾客可能给我们三种钱

  • 五块钱：我们直接收下，并且可以找零的前加上这五块钱
  • 十块：如果我们有五块钱，可以收下，同时把五块钱给顾客，否则无法招领
  • 二十块：二十块可以有两种找零法案。一种是找一个五块一个十块，一种是找三个五块。当两种找零方案都可行的时候更倾向于第一种，因为五块的应用场景更多。

    参考代码

    1. class Solution:
    2.   def lemonadeChange(self, bills: List[int]) -> bool:
    3.       five,ten = 0,0
    4.       for i,bill in enumerate(bills):
    5.           if bill == 5:
    6.               five += 1
    7.           elif bill == 10:
    8.               if five:
    9.                   five -= 1
    10.                   ten += 1
    11.               else:
    12.                   return False
    13.           else:
    14.               if ten and five:
    15.                   ten -= 1
    16.                   five -= 1
    17.               elif five >= 3:
    18.                   five -= 3
    19.               else: 
    20.                   return False
    21.       return True

    复杂度分析

    时间复杂度 O(n) n为bills的长度
    空间复杂度 O(1)