Leetcode+JAVA+貪心III

134.加油站

在一條環路上有?n?個加油站，其中第?i?個加油站有汽油?gas[i]?升。
你有一輛油箱容量無限的的汽車，從第?i?個加油站開往第?i+1?個加油站需要消耗汽油?cost[i]?升。你從其中的一個加油站出發，開始時油箱為空。
給定兩個整數數組?gas?和?cost?，如果你可以按順序繞環路行駛一周，則返回出發時加油站的編號，否則返回?-1?。如果存在解，則?保證?它是?唯一?的。
示例?1:
輸入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
輸出: 3
解釋:
從 3 號加油站(索引為 3 處)出發，可獲得 4 升汽油。此時油箱有 = 0 + 4 = 4 升汽油
開往 4 號加油站，此時油箱有 4 - 1 + 5 = 8 升汽油
開往 0 號加油站，此時油箱有 8 - 2 + 1 = 7 升汽油
開往 1 號加油站，此時油箱有 7 - 3 + 2 = 6 升汽油
開往 2 號加油站，此時油箱有 6 - 4 + 3 = 5 升汽油
開往 3 號加油站，你需要消耗 5 升汽油，正好足夠你返回到 3 號加油站。
因此，3 可為起始索引。
示例 2:
輸入: gas = [2,3,4], cost = [3,4,3]
輸出: -1
解釋:
你不能從 0 號或 1 號加油站出發，因為沒有足夠的汽油可以讓你行駛到下一個加油站。
我們從 2 號加油站出發，可以獲得 4 升汽油。 此時油箱有 = 0 + 4 = 4 升汽油
開往 0 號加油站，此時油箱有 4 - 3 + 2 = 3 升汽油
開往 1 號加油站，此時油箱有 3 - 3 + 3 = 3 升汽油
你無法返回 2 號加油站，因為返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，無論怎樣，你都不可能繞環路行駛一周。
提示:
n == gas.length == cost.length
1 <= n <= 105
0 <= gas[i], cost[i] <= 104
輸入保證答案唯一。

解題思路

問題核心：
有 n 個加油站，gas[i] 表示第 i 個加油站可加的油量，cost[i] 表示從第 i 到第 i+1 個加油站的耗油量。
油箱容量無限，初始為空，需找到一個起始站，使得汽車能繞環路一周（回到起點，油量非負）。
如果存在解，答案唯一；否則返回 -1。
貪心策略：
凈油量計算：
對于每個加油站，計算凈油量 res[i] = gas[i] - cost[i]，表示在站 i 加完油并開往下一站后的油量變化。
如果總凈油量 sum(res[i]) < 0，無法繞一周，返回 -1（因為總油量不足以覆蓋總消耗）。
起始點選擇：
使用 currSum 跟蹤從某個起始點開始的累計凈油量。
如果在某個點 i，currSum < 0，說明從當前起始點 start 到 i 的路徑不可行，重置 start = i + 1，并清零 currSum。
繼續遍歷，直到檢查所有站。
為什么貪心有效：
總油量檢查：如果 sum(res[i]) >= 0，存在至少一個解（題目保證唯一）。
局部失敗處理：如果從某個起點 start 到 i 的 currSum < 0，則 start 到 i 之間的任何點都不能作為起點（因為油量會更早變負）。
唯一解：題目保證如果解存在，則唯一。貪心算法通過排除不可行起點，找到唯一可行起點。
環形處理：
環形路徑通過數組循環模擬（i+1 模 n），但你的代碼通過單次遍歷和總和檢查隱式處理環形約束。
時間復雜度：
單遍遍歷數組：O(n)，其中 n 是 gas.length。
空間復雜度：O(n)（用于 res 數組），可優化為 O(1)（直接用 gas[i] - cost[i]）。

代碼?

import java.util.*;class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {// 創建凈油量數組，res[i] = gas[i] - cost[i]int[] res = new int[gas.length];// sum 記錄總凈油量，currSum 記錄當前路徑的凈油量int sum = 0, currSum = 0;// start 記錄潛在的起始加油站索引int start = 0;// 遍歷所有加油站for (int i = 0; i < res.length; i++) {// 計算第 i 個加油站的凈油量res[i] = gas[i] - cost[i];// 更新總凈油量sum += res[i];// 更新當前路徑凈油量currSum += res[i];// 如果當前路徑油量為負，當前起點不可行if (currSum < 0) {currSum = 0; // 重置當前路徑油量start = i + 1; // 將起點移到下一個加油站}}// 如果總凈油量 < 0，無法繞一周if (sum < 0) {return -1;}// 返回唯一可行起點（或 -1 如果 start 越界）return start;}
}

135.分發糖果

n?個孩子站成一排。給你一個整數數組?ratings?表示每個孩子的評分。
你需要按照以下要求，給這些孩子分發糖果：
每個孩子至少分配到?1?個糖果。
相鄰兩個孩子評分更高的孩子會獲得更多的糖果。
請你給每個孩子分發糖果，計算并返回需要準備的?最少糖果數目?。
示例?1：
輸入：ratings = [1,0,2]
輸出：5
解釋：你可以分別給第一個、第二個、第三個孩子分發 2、1、2 顆糖果。
示例?2：
輸入：ratings = [1,2,2]
輸出：4
解釋：你可以分別給第一個、第二個、第三個孩子分發 1、2、1 顆糖果。第三個孩子只得到 1 顆糖果，這滿足題面中的兩個條件。
提示：
n == ratings.length
1 <= n <= 2 * 104
0 <= ratings[i] <= 2 * 104

解題思路

問題核心：
給定數組 ratings，ratings[i] 表示第 i 個孩子的評分。
分配規則：
每個孩子至少 1 顆糖果。
如果 ratings[i] > ratings[i-1]，第 i 個孩子比第 i-1 個孩子多拿糖果。
如果 ratings[i] > ratings[i+1]，第 i 個孩子比第 i+1 個孩子多拿糖果。
目標：最小化總糖果數。
貪心策略：
初始化：
為每個孩子分配 1 顆糖果（滿足“至少 1 顆”）。
兩次遍歷：
從左到右：處理評分遞增的情況。如果 ratings[i] > ratings[i-1]，則 candies[i] = candies[i-1] + 1，確保左邊鄰居規則。
從右到左：處理評分遞減的情況。如果 ratings[i] > ratings[i+1]，則 candies[i] = max(candies[i], candies[i+1] + 1)，確保右邊鄰居規則，并保留左遍歷結果的最大值。
求和：累加 candies 數組，得到最小糖果數。
為什么貪心有效：
左遍歷確保評分遞增時糖果數遞增，滿足左側約束。
右遍歷修正評分遞減的情況，確保右側約束，同時取最大值避免破壞左遍歷結果。
兩次遍歷綜合考慮所有相鄰關系，保證滿足所有條件且糖果數最小。
時間復雜度：
初始化和兩次遍歷：O(n)。
求和：O(n)。
總計：O(n)。
空間復雜度：
O(n)（candies 數組）。

代碼

import java.util.*;class Solution {public int candy(int[] ratings) {// 獲取數組長度int n = ratings.length;// 初始化糖果數組，每個孩子至少 1 顆糖果int[] candies = new int[n];Arrays.fill(candies, 1);// 從左到右遍歷：處理評分遞增情況for (int i = 1; i < n; i++) {// 如果當前孩子評分高于前一個，分配更多糖果if (ratings[i] > ratings[i - 1]) {candies[i] = candies[i - 1] + 1;}}// 從右到左遍歷：處理評分遞減情況for (int i = n - 2; i >= 0; i--) {// 如果當前孩子評分高于后一個，確保糖果數大于后一個if (ratings[i] > ratings[i + 1]) {// 取當前糖果數和后一個糖果數+1的最大值，保留左遍歷結果candies[i] = Math.max(candies[i], candies[i + 1] + 1);}}// 計算總糖果數int sum = 0;for (int candy : candies) {sum += candy;}return sum;}
}

860.檸檬水找零

在檸檬水攤上，每一杯檸檬水的售價為?5?美元。顧客排隊購買你的產品，（按賬單?bills?支付的順序）一次購買一杯。
每位顧客只買一杯檸檬水，然后向你付?5?美元、10?美元或?20?美元。你必須給每個顧客正確找零，也就是說凈交易是每位顧客向你支付?5?美元。
注意，一開始你手頭沒有任何零錢。
給你一個整數數組?bills?，其中?bills[i]?是第?i?位顧客付的賬。如果你能給每位顧客正確找零，返回?true?，否則返回?false?。
示例 1：
輸入：bills = [5,5,5,10,20]
輸出：true
解釋：
前 3 位顧客那里，我們按順序收取 3 張 5 美元的鈔票。
第 4 位顧客那里，我們收取一張 10 美元的鈔票，并返還 5 美元。
第 5 位顧客那里，我們找還一張 10 美元的鈔票和一張 5 美元的鈔票。
由于所有客戶都得到了正確的找零，所以我們輸出 true。
示例 2：
輸入：bills = [5,5,10,10,20]
輸出：false
解釋：
前 2 位顧客那里，我們按順序收取 2 張 5 美元的鈔票。
對于接下來的 2 位顧客，我們收取一張 10 美元的鈔票，然后返還 5 美元。
對于最后一位顧客，我們無法退回 15 美元，因為我們現在只有兩張 10 美元的鈔票。
由于不是每位顧客都得到了正確的找零，所以答案是 false。
提示：
1 <= bills.length <= 105
bills[i]?不是?5?就是?10?或是?20?

解題思路

問題核心：
每位顧客支付 5、10 或 20 美元，購買一杯 5 美元的檸檬水，需找回 bill - 5 美元。
初始沒有零錢，只能用收到的鈔票找零。
目標：判斷是否能為所有顧客正確找零，返回 true 或 false。
貪心策略：
跟蹤零錢：
只需跟蹤 5 美元和 10 美元鈔票的數量（five 和 ten），因為 20 美元鈔票無法用于找零（題目中找零只涉及 5 美元和 10 美元）。
處理每種賬單：
5 美元：直接收下，增加 five++，無需找零。
10 美元：需找回 5 美元（10 - 5），消耗 1 張 5 美元鈔票（five--），增加 1 張 10 美元鈔票（ten++）。如果 five == 0，無法找零，返回 false。
20 美元：需找回 15 美元（20 - 5），有兩種找零方式：
優先用 1 張 10 美元 + 1 張 5 美元（ten--, five--），以保留更多 5 美元鈔票（因為 5 美元更靈活）。
如果沒有 10 美元鈔票，嘗試用 3 張 5 美元（five -= 3）。
如果兩者都不可行，返回 false。
為什么貪心有效：
優先使用 10 美元 + 5 美元找零 20 美元，減少對 5 美元鈔票的消耗，因為 5 美元鈔票對后續找零（10 美元或 20 美元）更關鍵。
每次決策局部最優（保留最多 5 美元鈔票），確保全局可行性。
如果某次無法找零，說明零錢不足，返回 false；否則，遍歷完成返回 true。
時間復雜度：
單遍遍歷 bills 數組：O(n)，其中 n 是 bills.length。
總計：O(n)。
空間復雜度：
O(1)，僅使用兩個變量（five 和 ten）。

代碼?

class Solution {public boolean lemonadeChange(int[] bills) {// 初始化 5 美元和 10 美元鈔票數量int five = 0, ten = 0;// 遍歷每位顧客支付的賬單for (int bill : bills) {if (bill == 5) {// 收到 5 美元，無需找零，增加 5 美元鈔票數量five++;} else if (bill == 10) {// 收到 10 美元，需找回 5 美元if (five == 0) {// 沒有 5 美元鈔票，無法找零return false;}five--; // 消耗 1 張 5 美元鈔票ten++;  // 增加 1 張 10 美元鈔票} else { // bill == 20// 收到 20 美元，需找回 15 美元if (ten > 0 && five > 0) {// 優先用 1 張 10 美元 + 1 張 5 美元找零ten--;five--;} else if (five >= 3) {// 否則用 3 張 5 美元找零five -= 3;} else {// 無法找零return false;}}}// 所有顧客都成功找零return true;}
}

406.根據身高重建隊列

假設有打亂順序的一群人站成一個隊列，數組?people?表示隊列中一些人的屬性（不一定按順序）。每個?people[i] = [hi, ki]?表示第?i?個人的身高為?hi?，前面?正好?有?ki?個身高大于或等于?hi?的人。
請你重新構造并返回輸入數組?people?所表示的隊列。返回的隊列應該格式化為數組?queue?，其中?queue[j] = [hj, kj]?是隊列中第?j?個人的屬性（queue[0]?是排在隊列前面的人）。
示例 1：
輸入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
輸出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
解釋：
編號為 0 的人身高為 5 ，沒有身高更高或者相同的人排在他前面。
編號為 1 的人身高為 7 ，沒有身高更高或者相同的人排在他前面。
編號為 2 的人身高為 5 ，有 2 個身高更高或者相同的人排在他前面，即編號為 0 和 1 的人。
編號為 3 的人身高為 6 ，有 1 個身高更高或者相同的人排在他前面，即編號為 1 的人。
編號為 4 的人身高為 4 ，有 4 個身高更高或者相同的人排在他前面，即編號為 0、1、2、3 的人。
編號為 5 的人身高為 7 ，有 1 個身高更高或者相同的人排在他前面，即編號為 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新構造后的隊列。
示例 2：
輸入：people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
輸出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]
提示：
1 <= people.length <= 2000
0 <= hi <= 106
0 <= ki < people.length
題目數據確保隊列可以被重建

解題思路

問題核心：
給定數組 people，people[i] = [hi, ki] 表示第 i 個人身高為 hi，前面有 ki 個身高大于或等于 hi 的人。
目標是構造隊列 queue，使得 queue[j] = [hj, kj] 表示隊列第 j 位的屬性，且滿足 ki 條件。
題目保證隊列可被重建，解唯一。
貪心策略：
排序：
按身高 hi 降序排序，若身高相同，則按 ki 升序排序。
理由：身高高的人應先安排，因為他們的 ki 表示前面高或等高的人數，優先處理高個子可以簡化后續插入（矮個子的 ki 不會受高個子影響）。
身高相同按 ki 升序，確保 ki 較小的人先插入（因為他們需要更靠前的位置）。
插入：
遍歷排序后的 people，將每個 person = [hi, ki] 插入到結果隊列的索引 ki 處。
插入時，ki 表示前面應有 ki 個高或等高的人。由于已按身高降序排序，之前插入的人身高大于或等于當前 hi，插入到 ki 位置正好滿足條件。
使用動態列表（ArrayList）支持按索引插入，插入后隊列自動調整。
轉換為數組：
將動態列表轉換為 int[][] 數組返回。
為什么貪心有效：
按身高降序排序確保高個子優先安排，矮個子插入時不會影響高個子的 ki（因為矮個子身高小于之前的人）。
按 ki 插入保證每個人的 ki 約束（前面正好有 ki 個高或等高的人）。
題目保證解存在，排序和插入策略確保唯一正確隊列。
時間復雜度：
排序：O(n log n)，其中 n 是 people.length。
插入：ArrayList 的插入操作為 O(n)，總共 n 次插入，O(n2)。
總計：O(n2)（插入操作主導）。
空間復雜度：
O(n)（queue 列表，不計輸出數組）。

代碼?

import java.util.*;class Solution {public int[][] reconstructQueue(int[][] people) {// 按身高降序排序，若身高相同則按 ki 升序排序Arrays.sort(people, (a, b) -> {if (a[0] != b[0]) return b[0] - a[0]; // 身高降序（高的先處理）return a[1] - b[1]; // 身高相同，ki 升序（小的 ki 先插入）});// 使用動態列表存儲重建的隊列List<int[]> queue = new ArrayList<>();// 遍歷排序后的數組，按 ki 插入到正確位置for (int[] person : people) {queue.add(person[1], person); // 在索引 person[1]（ki）處插入 person}// 將列表轉換為 int[][] 數組return queue.toArray(new int[people.length][]);}
}