思路： 使用 貪心算法 的思想

題目： 檸檬水找零
在檸檬水攤上，每一杯檸檬水的售價為5美元。顧客排隊購買你的產品,一次購買一杯。
每位顧客只買一杯檸檬水,然后向你付5美元、10美元或20美元。必須給每個顧客正確找零
注意,一開始你手頭沒有任何零錢。
如果你能給每位顧客正確找零,返回 true ，否則返回false

思路： 使用 貪心算法 的思想

• 本題中找零是不需要用到20美元的，但是需要用到 5 美元和 10 美元，因此需要記錄現在手上有多少張 5 美元和 10 美元。
• 5 美元：不需要找零，直接數量+1即可；
• 10 美元：只能找 5 美元，因此手上的 5 美元 -1，10 美元+1；
• 20 美元：有兩種方法：
  • 第一種：3 張 5 美元，顯然不是最優解，因為我們需要更多的 5美元來找零；
  • 第二種：一張 5 美元和 一張 10 美元，優先選擇該方式找零。

package bilibili;/*** @author: Arbicoral* @create: 2023-07-18 12:25* @Description: 貪心算法*/
public class GreedyByLemonChange {public static void main(String[] args) {System.out.println(change(new int[]{5, 10 ,20}));}private static boolean change(int[] arr) {int five = 0, ten = 0;//    表示手上有 5美元、10美元的個數for (int num : arr) {if (num == 5){++five;}if (num ==10) {if (five== 0){return false;//five不夠一個了，就返回false}--five;++ten;}if (num == 20){if (ten>=1 && five>=1){// 先判斷有沒有 5 10的，保證局部最優ten--;five--;} else if (five >= 3) {five -= 3;}else {return false;}}}return true;}
}