day29 贪心算法-gasStation+candy+lemonadeChange+queueReconstruction

### 8.9 134. Gas Station
There are n gas stations along a circular route, where the amount of gas at the ith station is gas`[i].
You have a car with an unlimited gas tank and it costs cost`[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations.
Given two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique
https://leetcode.cn/problems/gas-station/description/
https://programmercarl.com/0134.%E5%8A%A0%E6%B2%B9%E7%AB%99.html  
有补充，有消耗，统计每个节点的剩余油量即可。
1. 全局考虑：
情况一：如果gas的总和小于cost总和，那么无论从哪里出发，一定是跑不了一圈的
情况二：rest`[i] = gas[i]-cost[i]为一天剩下的油，i从0开始计算累加到最后一站，如果累加没有出现负数，说明从0出发，油就没有断过，那么0就是起点。
情况三：如果累加的最小值是负数，汽车就要从非0节点出发，从后向前，看哪个节点能把这个负数填平，能把这个负数填平的节点就是出发节点。

2. 局部考虑：
可以换一个思路，首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。
每个加油站的剩余量`rest[i]为gas[i] - cost[i]。
i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，因为这个区间选择任何一个位置作为起点，到i这里都会断油，那么起始位置从i+1算起，再从0计算curSum。
```java
public class gasStation {  
    public int canCompleteCircuit(int[] gas, int[] cost) {  
        int curSum = 0;//当前节点油耗情况  
        int totalSum = 0;//总油耗情况  
        int start = 0;  
        for (int i = 0; i < gas.length; i++) {  
            curSum += gas[i] - cost[i];  
            totalSum += gas[i] - cost[i];  
            //当前节点加油量不足以支撑车走到这个节点  
            if(curSum < 0){  
                //重新计算油箱剩余油量  
                curSum = 0;  
                //从当前节点的后一个再开始计算  
                start = i + 1;  
            }  
        }  
        if(totalSum < 0) return -1;  
        return start;  
    }  
}
```
### 8.10 135. Candy
There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.
You are giving candies to these children subjected to the following requirements:
Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.
Return the minimum number of candies you need to have to distribute the candies to the children.
https://leetcode.cn/problems/candy/description/
 135. 分发糖果 
本题涉及到一个思想，就是想处理好一边再处理另一边，不要两边想着一起兼顾，后面还会有题目用到这个思路 
https://programmercarl.com/0135.%E5%88%86%E5%8F%91%E7%B3%96%E6%9E%9C.html  
1.先从左到右遍历：右边孩子得分比左边高
2.再从右到左遍历
```java
public class candy {  
    public candy(){};  
    public int candy(int[] ratings) {  
        int[] candies = new int[ratings.length];  
        candies[0] = 1;  
        //从左到右遍历，如果右边的孩子比左边的孩子得分高，则让右边的孩子多吃一块糖  
        for (int i = 1; i < ratings.length; i++) {  
            candies[i] = (ratings[i] > ratings[i-1]) ? candies[i-1] + 1 : 1;  
        }  
        //从右向左遍历  
        for (int i = ratings.length-2; i >= 0; i--) {  
            if(ratings[i] > ratings[i+1]){  
                candies[i] = Math.max(candies[i+1]+1,candies[i]);  
            }  
        }  
        int sum = 0;  
        for (int i = 0; i < candies.length; i++) {  
            sum += candies[i];  
        }  
        return sum;  
    }  
}  
class candyTest {  
    public static void main(String[] args) {  
        candy example = new candy();  
        int[] rating = {1,2,2,1,3,2};  
        System.out.println(example.candy(rating));  
    }  
}
```
### 8.11 860. Lemonade Change
At a lemonade stand, each lemonade costs $5. Customers are standing in a queue to buy from you and order one at a time (in the order specified by bills). Each customer will only buy one lemonade and pay with either a $5, $10, or $20 bill. You must provide the correct change to each customer so that the net transaction is that the customer pays $5.
Note that you do not have any change in hand at first.
Given an integer array bills where bills[i] is the bill the ith customer pays, return true if you can provide every customer with the correct change, or false otherwise.
https://leetcode.cn/problems/lemonade-change/description/
860.柠檬水找零 
本题看上好像挺难，其实很简单，大家先尝试自己做一做。
https://programmercarl.com/0860.%E6%9F%A0%E6%AA%AC%E6%B0%B4%E6%89%BE%E9%9B%B6.html  
确实不难，自己写出来了。一开始写的有点问题，就是20的找钱可以找三个五块，这个情况漏了。
```java
public class lemonadeChange {  
    public lemonadeChange() {    }  
    public boolean lemonadeChange(int[] bills) {  
        if(bills[0] != 5) return false;  
        int chargeFive = 0;  
        int chargeTen = 0;  
  
        for (int i = 0; i < bills.length; i++) {  
            if(bills[i] == 10){  
                chargeFive--;  
                chargeTen++;  
            }else if(bills[i] == 20){  
                if(chargeTen == 0){  
                    chargeFive -= 3;  
                }else{  
                    chargeFive--;  
                    chargeTen--;  
                }          
            }else{  
                chargeFive++;  
            }  
            if(chargeFive < 0 || chargeTen < 0) return false;  
        }  
        return true;  
    }  
}
```

### 8.12 406. Queue Reconstruction by Height
You are given an array of people, people, which are the attributes of some people in a queue (not necessarily in order). Each people`[i] = [hi, ki] represents the ith person of height hi with exactly ki other people in front who have a height greater than or equal to hi.
Reconstruct and return the queue that is represented by the input array people. The returned queue should be formatted as an array queue, where queue`[j] = [hj, kj] is the attributes of the jth person in the queue (queue[0] is the person at the front of the queue).
https://leetcode.cn/problems/queue-reconstruction-by-height/description/
 406.根据身高重建队列 
本题有点难度，和分发糖果类似，不要两头兼顾，处理好一边再处理另一边。 
https://programmercarl.com/0406.%E6%A0%B9%E6%8D%AE%E8%BA%AB%E9%AB%98%E9%87%8D%E5%BB%BA%E9%98%9F%E5%88%97.html 
先把身高从高到低排序，根据k的大小将它插入队列。
不会的地方：
1. 二维数组排序巧妙解法
2. 根据k调整数组位置
```java
public class queueReconstruction {  
    public int[][] reconstructQueue(int[][] people) {  
        //sort people array via height in descend order firstly. if two people share the same height, I will sort them via k in ascend order.  
        //sort(T[] a, Comparator<? super T> c)        //Sorts the specified array of objects according to the order induced by the specified comparator.        Arrays.sort(people, (a, b) -> {  
            if(a[0] == b[0]) return a[1] - b[1];  
            return b[0] - a[0];}  
        );  
  
        LinkedList<int[]> result = new LinkedList<>();  
        for(int[] p : people){  
            //add(int index, E element): Inserts the specified element at the specified position in this list.  
            result.add(p[1],p);  
        }  
        return result.toArray(new int[result.size()][]);  
    }  
}
```