class Solution {
    public int findContentChildren(int[] g, int[] s) {
        //分别对孩子的胃口和饼干尺寸进行升序排序
        Arrays.sort(g);
        Arrays.sort(s);
        int max=0;
        int i=0,j=0;
        while(i<g.length&&j<s.length){
            if(s[j] >= g[i]){
                max++;
                i++;
                j++;
            }else{
                j++;
            }
        }
        return max;
    }
}

class Solution {
    public int wiggleMaxLength(int[] nums) {
        //仅有一个元素序列也视作摆动序列。
        if(nums.length==1){
            return 1;
        }
        //一个元素也算摆动，所以就不考虑最后一个元素了，遍历完倒数第二个元素就结束。因此rslt初始值设为1(即算上了最后一个元素)
        int rslt=1;
        //一个元素的前差和后差
        int pre=0;//★假设第一个元素前有一个相同元素，所以pre初始是0!
        int cur=0;
        //遍历完倒数第二个元素就结束
        for(int i=0;i<nums.length-1;i++){
            //前差通过后差获得
            //计算后差(遍历完倒数第二个元素就结束,所以i+1不会报错)
            cur=nums[i+1]-nums[i];
            //情况①当前元素前后差值一正一负,即(pre>0&&cur<0)||(pre<0&&cur>0),当前元素是摆动
            //★情况②相邻元素相同，这里算最左边的那个相同元素，即pre==0&&cur!=0，这几个相邻相同元素算一次摆动
            if((pre>=0&&cur<0)||(pre<=0&&cur>0)){
                rslt++;
                //★更新前差:下一个元素的前差是现在的后差
                pre=cur;
            }
        }
        return rslt;
    }
}

public int maxSubArray(int[] nums) {
    int rslt=Integer.MIN_VALUE;
    int sum=0;
    for(int i=0;i<nums.length;i++){
        sum+=nums[i];
        //★因为nums可能全是负数，所以无论sum大于0还是小于0，都需要更新rslt。
        rslt=sum>rslt?sum:rslt;
        //如果当前连续和小于0了
        if(sum<0){
            //重置sum，相当于从下个位置重新求和
            sum=0;
        }
    }
    return rslt;
}

class Solution {
    public int maxProfit(int[] prices) {
        int sum=0;
        for(int i=0;i<prices.length-1;i++){
            int cha=prices[i+1]-prices[i];
            if(cha>0){
                sum+=cha;
            }
        }
        return sum;
    }
}

class Solution {
    public int jump(int[] nums) {
        if(nums.length==1) return 0;
        //当前这一次能跳到的最远位置
        int curReach=0;
        //下一步能跳到的最远位置
        int nextReach=0;
        int count=0;
        for(int i=0;i<nums.length;i++){
            //★更新下一步能跳到的最远位置，来保证每一次跳跃都是最远的
            nextReach=Math.max(i+nums[i],nextReach);
            //如果下一步能跳到最后一个位置，count+1，结束
            if(nextReach>=nums.length-1){
                return count+1;
            }
            //下一步不能跳到，现在所处的位置是否是当前能跳到的最远位置，如果是，就需要再跳一次
            if(i==curReach){
                //再跳一次
                count++;
                //更新这一次的最远位置
                curReach=nextReach;
            }
        }
        return count;
    }
}

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        int sum=0;
        Arrays.sort(nums);
        for(int i=0;i<nums.length;i++){
            //如果k还有次数，就将负数取反
            if(k>0&&nums[i]<0){
                nums[i]=-nums[i];
                k--;
            }
            sum+=nums[i];
        }
        //★将所有正数再排序，方便确定最小的正数
        Arrays.sort(nums);
        //如果k还有次数，说明nums中所有负数都取反了，现在nums中全是非负数
        if(k>0){
            //如果剩的k是偶数，直接返回sum，因为正数取反两次还是正数
            if(k%2==0){
                return sum;
            }else{//k剩的是奇数
                //只需要将最小的数取反，对sum进行处理
                sum=sum-nums[0]*2;
            }
        }
        //k没有次数了
        return sum;
    }
}

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int start=0;
        //经过若干加油站后剩的所有油
        int restSum=0;
        //★经过所有加油站剩的油
        int totalSum=0;
        for(int i=0;i<gas.length;i++){
            //从出发到当前加油站共剩的油
            restSum=restSum+(gas[i]-cost[i]);
            //经过全部加油站剩的油
            totalSum=totalSum+(gas[i]-cost[i]);
            //如果经过当前加油站后，油箱剩的油为负数了，说明到不了下一个加油站，更新起始位置，重置油箱
            if(restSum<0){
                start=i+1;
                restSum=0;
            }
        }
        //★如果经过所有加油站后剩的油为负，那么无论如何都转不了一圈(这就是为什么需要totalSum)
        if(totalSum<0){
            return -1;
        }else{
            return start;
        }
    }
}

class Solution {
    public int candy(int[] ratings) {
        //每个孩子需要分几颗
        int[] num=new int[ratings.length];
        //★正序遍历与左边孩子比较
        //第一个孩子的左边没有其他孩子，先给1颗
        num[0]=1;
        for(int i=1;i<ratings.length;i++){
            //如果比左孩子分高，比左孩子多给一颗
            //如果比左孩子分低或同分，只给1颗
            num[i]=ratings[i]>ratings[i-1]?num[i-1]+1:1;
        }
        //倒序与右边孩子比较(最后一个孩子右边没有孩子)
        for(int i=ratings.length-2;i>=0;i--){
            //如果比右边孩子分高
            if(ratings[i]>ratings[i+1]){
                //★取满足左右两边评分比较的最大糖数
                                //num[i+1]+1是与右边孩子比较得出应该分的糖数，num[i]是与左边孩子比较得出应该分的糖数。取二者大的，才能保证满足与左右两边都比较。
                num[i]=Math.max(num[i+1]+1,num[i]);
            }
        }
        //求一共几颗糖
        int count=0;
        for(int i=0;i<num.length;i++){
            count+=num[i];
        }
        return count;
    }
}

class Solution {
    public boolean lemonadeChange(int[] bills) {
        //手里面额为5和10的钱的张数，一开始手里没钱
        int five=0;
        int ten=0;
        for(int i=0;i<bills.length;i++){
            if(bills[i]==5){//不找
                five++;
            }else if(bills[i]==10){//找5块
                five--;
                ten++;
            }else{//找15
                //★有10优先用10+5进行找零
                if(ten>0){
                    ten--;
                    five--;
                }else{//没有10的用三个5找
                    five-=3;
                }
            }
            //找完零后手里还欠钱
            if(five<0||ten<0){
                return false;
            }
        }
        return true;
    }
}

class Solution {
    public int findMinArrowShots(int[][] points) {
        //对气球按左边界升序排序
                //★使用Integer内置比较方法，不会溢出
        Arrays.sort(points,(a,b)->Integer.compare(a[0],b[0]));
        //points不为空，所以至少需要1支箭
        int count=1;
        //因为第一个气球(下标0)跟前一个气球(根本没有)一定不会重合，所以从下标为1的第二个气球开始遍历
        for(int i=1;i<points.length;i++){
            //当前气球与上一个气球有重叠，暂时不需要射箭
            if(points[i][0]<=points[i-1][1]){
                //★更新重叠部分的最小右边界(因为当前气球可能完全在前一个气球里面)，用来判断后面的气球是否与重叠部分再重叠
                points[i][1]=Math.min(points[i-1][1],points[i][1]);
            }else{
                //当前气球与上一个气球不重叠，需要射1支箭
                count++;
            }
        }
        return count;
    }
}

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        int count=0;
        //对所有区间按左边界升序排序
        Arrays.sort(intervals,(a,b)->Integer.compare(a[0],b[0]));
        //下标为0的第一个区间没有前一个区间，所以从下标1开始遍历
        for(int i=1;i<intervals.length;i++){
            //重叠
            if(intervals[i][0]<intervals[i-1][1]){
                //更新重叠区域的最小右边界（为了移除范围大的那个区间）
                intervals[i][1]=Math.min(intervals[i-1][1],intervals[i][1]);
                //有重叠，就要移除
                count++;
            }
        }
        return count;
    }
}

class Solution {
    public List<Integer> partitionLabels(String s) {
        List<Integer> rslt=new ArrayList<>();
        int len=0;
        //用来记录每个字母出现的最远位置
        int[] position=new int[26];
        char[] arr=s.toCharArray();
        //记录每个字母出现的最远位置
        for(int i=0;i<arr.length;i++){
            position[arr[i]-'a']=i;
        }
        //片段的起始和终止位置[]
        int start=0;
        int end=0;
        for(int i=0;i<arr.length;i++){
            //更新当前片段的终止位置
            end=Math.max(end,position[arr[i]-'a']);
            //★如果到达当前片段的终止位置，切割片段
            if(i==end){
                //计算片段长度
                len=end-start+1;
                rslt.add(len);
                //★更新下一个片段的起始位置
                start=end+1;
            }
        }
        return rslt;
    }
}

class Solution {
    public int[][] merge(int[][] intervals) {
        List<int[]> rslt=new LinkedList<>();
        //按左边界升序排序
        Arrays.sort(intervals,(a,b)->Integer.compare(a[0],b[0]));
        //将第一个区间加进去(如果只有一个区间，这也是结果集了)
        rslt.add(intervals[0]);
        for(int i=1;i<intervals.length;i++){
            //如果当前区间的左边界小于等于前一个区间的右边界，则重叠
            if(intervals[i][0]<=intervals[i-1][1]){
                //合并当前区间与上一个区间
                intervals[i][0]=intervals[i-1][0];//左区间取最左边界(按左边界升序排序了)
                intervals[i][1]=Math.max(intervals[i][1],intervals[i-1][1]);//右边界取最右边界
                //移除结果集最后一个区间(因为这个区间合并了当前区间，二者成了新的合并区间)
                rslt.remove(rslt.size()-1);
                //将合并区间加入结果集
                rslt.add(new int[]{intervals[i][0],intervals[i][1]});
            }else{
                //不重叠，直接将该区间加进去
                rslt.add(intervals[i]);
            }
        }
        return rslt.toArray(new int[rslt.size()][]);
    }
}

class Solution {
    public int monotoneIncreasingDigits(int n) {
        //1234 -> "1234"
        String nStr=String.valueOf(n);
        char[] arr=nStr.toCharArray();
        //★用来记录从哪开始往后都是9
        //★start初始值为arr.length是为了当n为个位数时，跳过赋'9'的for循环!
        int start=arr.length;
        //从低位向高位遍历(千 百 十 个)
        for(int i=arr.length-1;i>=1;i--){
            //★如果高位比低位大，就让高位-1，【所有】低位都变9，这样就能得到最大单调递增数
            if(arr[i-1]>arr[i]){
                arr[i-1]--;
                //更新start
                start=i;
            }
        }
        //从start开始都为9
        for(int i=start;i<arr.length;i++){
            arr[i]='9';
        }
        //char[]->string->int
        //★parseInt("0023")会自动转为整数23.
        return Integer.parseInt(String.valueOf(arr));
    }
}

public int maxProfit(int[] prices, int fee) {
    //利润
    int rslt=0;
    //表示【算上手续费】，买入股票的最低价格
    int buy=prices[0]+fee;
    for(int i=1;i<prices.length;i++){
        //情况1:如果当前价格加上手续费比我们手头的买入价格低，就用现在的price+fee买入
        if(prices[i]+fee<buy){
            //更新buy
            buy=prices[i]+fee;
        }else if(prices[i]>buy){//情况2:如果当前价格比买入价格高，我们就【假装卖出】，因为可能明天的价格还会上涨
            //假装卖出时的利润
            rslt=rslt+prices[i]-buy;
            //★只是假装卖掉，下一天可能还会涨价，所以现在我们相当于以prices[i]买入了一只股票(更新buy)，这样如果明天价格上涨，就又能加上这两天的利润了
            buy=prices[i];
        }
        //情况3:当前价格没有低到我们放弃手上的股票去选择它，也没有高到我们可以通过卖出获得收益，直接跳过
    }
    return rslt;
}

• 情况1：左右孩子都被覆盖了，那么当前节点就是无覆盖。
          所以要让一开始叶子节点就是无覆盖，那么空节点应该都被覆盖！
  
• 情况2：左右孩子至少有一个没被覆盖，那么当前节点就要装摄像头。
          这个不难理解，毕竟有一个孩子没有覆盖，父节点就应该放摄像头。
• 情况3：左右孩子至少有一个装了摄像头，那么当前节点就是被覆盖。
• ★情况4：头结点没被覆盖，递归结束单独处理。
          递归结束之后，可能头结点还没被覆盖：
          

class Solution {
    int rslt=0;
    public int minCameraCover(TreeNode root) {
        //★情况4:递归完了头结点还没被覆盖
        if(countCamera(root)==0){
            rslt++;
        }
        return rslt;
    }
    public int countCamera(TreeNode root){
        //终止条件——空节点被覆盖
        if(root==null)  return 2;
        //递归逻辑——后序遍历
        //左、右节点的状态
        int left=countCamera(root.left);
        int right=countCamera(root.right);
        //中——对当前节点进行处理(三种情况)
        //情况1:如果左右都被覆盖，当前节点未覆盖
        if(left==2&&right==2) return 0;
        //情况2:如果左右至少一个没被覆盖，当前节点装摄像头
        if(left==0||right==0){
            rslt++;
            return 1;
        }
        //情况3:如果左右至少一个有摄像头，当前节点被覆盖
        if(left==1||right==1) return 2;
        //★不加会报无返回值的错误，只是为了有个返回值不报错，其实根本到不了这里，没有实际意义
        return -1;
    }
}