860.檸檬水找零

參考視頻：貪心算法，看上去復(fù)雜，其實(shí)邏輯都是固定的！LeetCode：860.檸檬水找零_嗶哩嗶哩_bilibili?

解題思路：

只需要維護(hù)三種金額的數(shù)量，5，10和20。

有如下三種情況：

情況一：賬單是5，直接收下。
情況二：賬單是10，消耗一個(gè)5，增加一個(gè)10
情況三：賬單是20，優(yōu)先消耗一個(gè)10和一個(gè)5，如果不夠，再消耗三個(gè)5
此時(shí)大家就發(fā)現(xiàn) 情況一，情況二，都是固定策略，都不用我們來做分析了，而唯一不確定的其實(shí)在情況三。

而情況三邏輯也不復(fù)雜甚至感覺純模擬就可以了，其實(shí)情況三這里是有貪心的。

賬單是20的情況，為什么要優(yōu)先消耗一個(gè)10和一個(gè)5呢？

因?yàn)槊涝?0只能給賬單20找零，而美元5可以給賬單10和賬單20找零，美元5更萬能！

所以局部最優(yōu)：遇到賬單20，優(yōu)先消耗美元10，完成本次找零。全局最優(yōu)：完成全部賬單的找零。

局部最優(yōu)可以推出全局最優(yōu)，并找不出反例，那么就試試貪心算法！
?

public class Leetcode860 {public boolean lemonadeChange(int[] bills) {int five = 0;int ten = 0;for (int i = 0; i < bills.length; i++) {if (bills[i] == 5) {five++;} else if (bills[i] == 10) {if (five < 1) {return false;}five--;ten++;} else if (bills[i] == 20) {if (ten >= 1 && five >= 1) {ten--;five--;} else if (five >= 3) {five -= 3;} else {return false;}}}return true;}
}

406.根據(jù)身高重建隊(duì)列

解題思路：

那么按照身高h(yuǎn)來排序呢，身高一定是從大到小排（身高相同的話則k小的站前面），讓高個(gè)子在前面。

此時(shí)我們可以確定一個(gè)維度了，就是身高，前面的節(jié)點(diǎn)一定都比本節(jié)點(diǎn)高！

那么只需要按照k為下標(biāo)重新插入隊(duì)列就可以了，為什么呢？

public class Leetcode406 {public int[][] reconstructQueue(int[][] people) {Arrays.sort(people, (a, b) -> {if (a[0] == b[0]) return a[1] - b[1];return b[0] - a[0];});LinkedList<int[]> que = new LinkedList<>();for (int[] p : people) {que.add(p[1], p);}return que.toArray(new int[people.length][]);}
}

452. 用最少數(shù)量的箭引爆氣球

解題思路：

如何使用最少的弓箭呢？

直覺上來看，貌似只射重疊最多的氣球，用的弓箭一定最少，那么有沒有當(dāng)前重疊了三個(gè)氣球，我射兩個(gè)，留下一個(gè)和后面的一起射這樣弓箭用的更少的情況呢？

嘗試一下舉反例，發(fā)現(xiàn)沒有這種情況。

那么就試一試貪心吧！局部最優(yōu)：當(dāng)氣球出現(xiàn)重疊，一起射，所用弓箭最少。全局最優(yōu)：把所有氣球射爆所用弓箭最少。

算法確定下來了，那么如何模擬氣球射爆的過程呢？是在數(shù)組中移除元素還是做標(biāo)記呢？

如果真實(shí)的模擬射氣球的過程，應(yīng)該射一個(gè)，氣球數(shù)組就remove一個(gè)元素，這樣最直觀，畢竟氣球被射了。

但仔細(xì)思考一下就發(fā)現(xiàn)：如果把氣球排序之后，從前到后遍歷氣球，被射過的氣球僅僅跳過就行了，沒有必要讓氣球數(shù)組remove氣球，只要記錄一下箭的數(shù)量就可以了。

以上為思考過程，已經(jīng)確定下來使用貪心了，那么開始解題。

為了讓氣球盡可能的重疊，需要對(duì)數(shù)組進(jìn)行排序。

那么按照氣球起始位置排序，還是按照氣球終止位置排序呢？

其實(shí)都可以！只不過對(duì)應(yīng)的遍歷順序不同，我就按照氣球的起始位置排序了。

既然按照起始位置排序，那么就從前向后遍歷氣球數(shù)組，靠左盡可能讓氣球重復(fù)。

從前向后遍歷遇到重疊的氣球了怎么辦？

如果氣球重疊了，重疊氣球中右邊邊界的最小值 之前的區(qū)間一定需要一個(gè)弓箭。

以題目示例： [[10,16],[2,8],[1,6],[7,12]]為例，如圖：（方便起見，已經(jīng)排序）
?

public class Leetcode452 {public int findMinArrowShots(int[][] points) {Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));int res = 0;for (int i = 1; i < points.length; i++) {if (points[i][0] > points[i - 1][1]) {res++;}if (points[i][0] <= points[i - 1][1]) {points[i][1] = Math.min(points[i - 1][1], points[i][1]);}}return res;}
}