Задача с собеседования в Zalando

Задача с собеседования в Zalando В лимонадном киоске один стакан лимонада стоит 5 долларов. Покупатели стоят в очереди и приобретают лимонад в порядке, указанном в массиве bills. Каждый клиент покупает только один лимонад и платит одной из следующих купюр: 5, 10 или 20 долларов. Вам необходимо дать правильную сдачу каждому клиенту, чтобы итоговая сумма, которую он заплатил, составила ровно 5 долларов. Имейте в виду, что вначале у вас нет денег для сдачи. Задан целочисленный массив bills, где bills[i] - это купюра, которой расплачивается i-й любитель лимонада. Верните true, если можете дать правильную сдачу каждому клиенту, или false в противном случае. Пример 1: Input: bills = [5,5,5,10,20] Output: true Пример 2: Input: bills = [5,5,10,10,20] Output: false Чат алгоритмистов Решение Создаём переменные для хранения купюр, переменная twenty нам не нужна, потому что не будет использоваться в качестве сдачи. Проходим по каждому элементу в массиве и обрабатываем платежи, увеличивая (принимая купюру) и/или уменьшая (при необходимости сдачи) счётчик переменной. Проверяем возможность дать клиенту сдачу при каждом платеже, применяя жадный алгоритм. Ищем наиболее оптимальное решение на каждом шаге: При оплате 10$ - выбора нет, отдаём купюру номиналом 5, и это наиболее оптимально в данном случае. Но если клиент платит 20$, предпочитаем дать сдачу с использованием купюры наибольшего номинала (10+5, а не 5+5+5), так как 5$ более универсальны и чаще могут понадобиться для размена. Сложность O(n) - по времени O(1) - по памяти Код class Solution: def lemonadeChange(self, bills: List[int]) -> bool: five = 0 ten = 0 for b in bills: if b == 5: five += 1 elif b == 10: if five < 1: return False else: five -= 1 ten += 1 else: if five >= 1 and ten >= 1: ten -= 1 five -= 1 elif five >= 3: five -= 3 else: return False return True @algoses