LeetCode 860. 柠檬水找零

Categories:

题目描述
思路分析
1. 解法一：贪心（推荐）
相似题目

题目描述

✅ 860. 柠檬水找零

思路分析

解法一：贪心（推荐）

核心思路：

顾客只可能支付 5 元、10 元或 20 元，只需维护手中 5 元和 10 元的数量

收到 5 元：直接收下，5 元计数加一

收到 10 元：需找零 5 元，若没有 5 元则失败；10 元计数加一，5 元计数减一

收到 20 元：优先用 10 元 + 5 元找零（保留更多 5 元应对后续），若不行则用 3 张 5 元，否则失败

贪心关键：5 元比 10 元更”通用”（10 元只能找 20 元的零，而 5 元能找 10 元和 20 元的零），所以优先消耗 10 元

复杂度分析：

时间复杂度：O(n)，其中 n 为顾客数量，遍历一次数组

空间复杂度：O(1)，只使用常数个变量

class Solution {
  public boolean lemonadeChange(int[] bills) {
    // 分别记录手中 5 元和 10 元的数量
    int five = 0;
    int ten = 0;

    for (int bill : bills) {
      if (bill == 5) {
        // 收到 5 元，无需找零
        five++;
      } else if (bill == 10) {
        // 收到 10 元，找零 5 元
        if (five == 0) {
          return false;
        }
        five--;
        ten++;
      } else {
        // 收到 20 元，优先用 10+5 找零，否则用 3 张 5 元
        if (ten > 0 && five > 0) {
          ten--;
          five--;
        } else if (five >= 3) {
          five -= 3;
        } else {
          return false;
        }
      }
    }

    return true;
  }
}

func lemonadeChange(bills []int) bool {
    // 分别记录手中 5 元和 10 元的数量
    five, ten := 0, 0

    for _, bill := range bills {
        if bill == 5 {
            // 收到 5 元，无需找零
            five++
        } else if bill == 10 {
            // 收到 10 元，找零 5 元
            if five == 0 {
                return false
            }
            five--
            ten++
        } else {
            // 收到 20 元，优先用 10+5 找零，否则用 3 张 5 元
            if ten > 0 && five > 0 {
                ten--
                five--
            } else if five >= 3 {
                five -= 3
            } else {
                return false
            }
        }
    }

    return true
}

相似题目

题目	难度	考察点
135. 分发糖果	困难	贪心
455. 分发饼干	简单	贪心
406. 根据身高重建队列	中等	贪心
621. 任务调度器	中等	贪心
738. 单调递增的数字	中等	贪心

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/31487113