贪心的本质是选择每一阶段的局部最优，从而达到全局最优。

手动模拟一下感觉可以局部最优推出整体最优，而且想不到反例，那么就试一试贪心。
贪心没有套路，说白了就是常识性推导加上举反例。

题型总结

455 分饼干
从代码中可以看出我用了一个 index 来控制饼干数组的遍历，遍历饼干并没有再起一个 for 循环，而是采用自减的方式，这也是常用的技巧。
有的同学看到要遍历两个数组，就想到用两个 for 循环，那样逻辑其实就复杂了

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int j=0;//控制胃口的遍历
        int count=0;//满足的总人数
        for(int i=0;i<s.length && j < g.length;i++){
            if(s[i]>=g[j]){//从最小的饼干开始看能喂饱谁
                j++;//这样一个for遍历就行了。
                count++;
            }
        }
        return count;
    }
}

区间问题

区间问题：
55 45两跳跃 763.划分字母区间 这三题都是要更新最大索引
452用最少数量的箭引爆气球 453使其无重叠区间 56合并区间 这三题区别就是在于对重叠区间的处理不同

452 435 56 处理重叠时的逻辑不一样是因为 前两个删除就要更新最小右边界。后一个添加就是更新最大右边界。

45 跳跃游戏

class Solution {
    public int jump(int[] nums) {
       if(nums==null||nums.length==0||nums.length==1) return 0;
       int count=0;//记录跳跃的次数
       int curconver=0;//记录当前覆盖的最大区域
       int maxconver=0;//最大的覆盖区域

       for(int i=0;i<nums.length;i++){
        maxconver=Math.max(maxconver,i+nums[i]);
        //说明当前一步，再跳一步就到达了末尾
        if(maxconver>=nums.length-1){
            count++;
            break;
        }
         //走到当前覆盖的最大区域时，更新下一步可达的最大区域
        if(i==curconver){
            curconver=maxconver;
            count++;
        }
       }
       return count++;
}
}

452用最少数量的箭引爆气球

class Solution {
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points,(a,b)->Integer.compare(a[0],b[0]));

        int count=1;// points不为空初始射一箭，后面两球没有重叠再射一剑，重叠不用管。
        for(int i=1;i<points.length;i++){
            if(points[i][0]>points[i-1][1])//points[i][0] 0是第i个气球的左端点，1是右端点。
            //也就是右边的左端点大于临近左边气球的右端点。也就是临近的这两个气球没有重叠部分时。
            {
                  count++;  
            }else{
                points[i][1]=Math.min(points[i][1],points[i-1][1]);//维护当前箭能覆盖的最小右边界
            }
            
        }
        return count;
    }
}

435.无重叠区间

和452其实是一类题；记得二维数组先排序。然后画图找重叠逻辑。右边东西的左边界大于左边东西的右边界就是有重叠区间。如果要移除，要记得更新移除后的最小右边界。

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals,(a,b)->Integer.compare(a[0],b[0]));
        int count=0;
        for(int i=1;i<intervals.length;i++){
            if(intervals[i][0]<intervals[i-1][1]){
                count++;//临近的有重叠部分
                 intervals[i][1]=Math.min(intervals[i][1],intervals[i-1][1]);//移除上一个重叠的，所以要更新
            }
        }

        return count;
    }
}

56 合并区间

和前面两个区别在于 对于重叠的区间不是删除而是合并添加。

class Solution {
    public int[][] merge(int[][] intervals) {
          List<int[]> res = new LinkedList<>();//每个节点存储一个 int[] 类型的数组

          if (intervals.length == 0) 
          {
            return intervals;
        }
       Arrays.sort(intervals, (x, y) -> Integer.compare(x[0], y[0]));
        //区间初始化为第一个
        int start = intervals[0][0];
        int rightmostRightBound = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            //如果当前的左边界大于前面最大右边界，也就是无重叠。
            if (intervals[i][0] > rightmostRightBound) {
                //当前区间不重叠加入到结果中。
                res.add(new int[]{start, rightmostRightBound});
                //记录当前的数组区间，如果和下一个还不重叠就再次加到res里。
                start = intervals[i][0];
                rightmostRightBound = intervals[i][1];
            } else {//重叠了要合并，更新最右边界就行了。结果不在这添加，因为可能好几个重叠的。
                //更新最大右边界
                rightmostRightBound = Math.max(rightmostRightBound, intervals[i][1]);
            }
        }
        // 添加最后一个合并的区间
        res.add(new int[]{start, rightmostRightBound});
        // 将List<int[]>转为int[][]
        return res.toArray(new int[res.size()][]);
    }
}

763.划分字母区间

将字符串分割，使得每个部分中的字符不会出现在其他部分中（即每个字符只属于一个片段）。

class Solution {
    public List<Integer> partitionLabels(String s) {
        char[] chars=s.toCharArray();//字符串s先转成char数组。
        List<Integer> result = new LinkedList<>();
        int lastIndex = 0; // 当前片段的最后位置
        int start = 0;     // 当前片段的起始位置
        for(int i=0;i<chars.length;i++){
            // 找到当前字符在字符串中最后出现的位置
            int currentLast = s.lastIndexOf(chars[i]);
            // 更新当前片段的最后位置
            lastIndex = Math.max(lastIndex, currentLast);
            // 如果当前位置等于当前片段的最后位置，说明可以分割
            if (i == lastIndex) {
                result.add(lastIndex - start + 1); // 计算片段长度并加入结果
                start = i + 1; // 更新下一个片段的起始位置
            }
        }
        return result;
    }
}

股票问题 求最大的利润

买卖限次数问题 以及 冷冻期问题，设立状态，整个流程可以抽象成m个状态，那dp就用二维的表示第i天第m个状态时利润的最大值。
dp初始化：m为买入时初始为-price[0],卖出或者冷冻初始化为0就行了。

121.买卖股票的最佳时机 只能买卖一次

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

class Solution {
    public int maxProfit(int[] prices) {
        int result=0;
        int low=prices[0];
        for(int i=0;i<prices.length;i++){
            low=Math.min(prices[i],low);
            result=Math.max(prices[i]-low,result);
        }
        return result;
    }
}

122.买卖股票的最佳时机 II 可以买卖多次

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大利润 。

使用贪心策略不用关心具体什么时候买卖，只要收集每天的正利润，最后稳稳的就是最大利润了。

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

714.买卖股票的最佳时机含手续费 可以买卖多次

本题有了手续费，就要关心什么时候买卖了，因为计算所获得利润，需要考虑买卖利润可能不足以扣减手续费的情况。
买入日期：其实很好想，遇到更低点就记录一下。
卖出日期：这个就不好算了，但也没有必要算出准确的卖出日期，只要当前价格大于（最低价格+手续费），就可以收获利润，至于准确的卖出日期，就是连续收获利润区间里的最后一天（并不需要计算是具体哪一天）。

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int buy=prices[0]+fee;//假设第一天就买了
        int sum=0;
        for(int p:prices){
            if(p+fee<buy)//说明第一天买的不合算啊
            {
                buy=p+fee;//更新，这时候才买。
            }
            else if(p>buy){
                sum=sum+p-buy;
                buy=p;//卖出后更新，比p小的时候就买
            }
        }
        return sum;
    }
}

122.买卖股票的最佳时机II 最多买卖两次 第一次卖是最低成本

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

class Solution {
    public int maxProfit(int[] prices) {
        // 初始化四个状态
        int firstBuy = Integer.MAX_VALUE; // 第一次买入的最低价格
        int firstSell = 0;                 // 第一次交易的最大利润
        int secondBuy = Integer.MIN_VALUE; // 第二次买入后的剩余金额（考虑第一次利润）
        int secondSell = 0;                 // 第二次交易后的总利润
        
        for (int price : prices) {
            // 1. 更新第一次买入的最低成本
            firstBuy = Math.min(firstBuy, price);
            // 2. 更新第一次卖出的最大利润
            firstSell = Math.max(firstSell, price - firstBuy);
            // 3. 更新第二次买入后的剩余金额（需叠加第一次利润）
            secondBuy = Math.max(secondBuy, firstSell - price);
            // 4. 更新第二次卖出的总利润
            secondSell = Math.max(secondSell, secondBuy + price);
        }
        return secondSell;
    }
}

188.买卖股票的最佳时机IV k笔交易

给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

class Solution {
    public int maxProfit(int k, int[] prices) {
        int[] dp=new int[2*k];//偶数索引表示进行第i次交易的买入状态，奇数表示卖出
        //初始化
        for(int i=0;i<2*k;i++){
            if(i%2==0) dp[i]=-prices[0];//每次交易的买入
            else dp[i]=0;//每次交易的卖出
        }

        for(int i=0;i<prices.length;i++){// 遍历每一天
            for(int j=0;j<2*k;j++){ // 遍历每个交易状态
                if(j%2==0){ // 买入状态
                    if(j>0){
                        dp[j]=Math.max(dp[j],dp[j-1]-prices[i]);
                    }else{
                        dp[j]=Math.max(dp[j],-prices[i]);//第一次买入
                    }
                }else{ // 卖出状态
                        dp[j]=Math.max(dp[j],dp[j-1]+prices[i]);
                }
            }
        }
        return dp[2*k-1];
    }
}

309.最佳买卖股票时机含冷冻期

给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。​
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
dp[i][j]，第i天状态为j，所剩的最多现金为dp[i][j]。
具体可以区分出如下四个状态：
状态一：持有股票状态（今天买入股票，或者是之前就买入了股票然后没有操作，一直持有）
不持有股票状态，这里就有两种卖出股票状态
状态二：保持卖出股票的状态（两天前就卖出了股票，度过一天冷冻期。或者是前一天就是卖出股票状态，一直没操作）
状态三：今天卖出股票
状态四：今天为冷冻期状态，但冷冻期状态不可持续，只有一天！
然后写出每个状态对应的递推公式。

dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3], dp[i - 1][1]) - prices[i]);
dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);
dp[i][2] = dp[i - 1][0] + prices[i];
dp[i][3] = dp[i - 1][2];

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) return 0;
        
        int n = prices.length;
        // dp[i][j]：第i天状态为j时的最大利润
        // j的四个状态：
        // 0: 持有股票
        // 1: 保持卖出股票状态（非冷冻期）
        // 2: 今天卖出股票
        // 3: 冷冻期
        int[][] dp = new int[n][4];
        
        // 初始化
        dp[0][0] = -prices[0]; // 第一天买入
        dp[0][1] = 0;          // 第一天无法保持卖出状态
        dp[0][2] = 0;          // 第一天无法卖出
        dp[0][3] = 0;          // 第一天无冷冻期
        
        for (int i = 1; i < n; i++) {
            // 状态0：持有股票（可能是之前买入，或今天从非冷冻期/保持卖出状态买入）
            dp[i][0] = Math.max(
                dp[i - 1][0], // 保持持有
                Math.max(
                    dp[i - 1][1], // 从保持卖出状态买入
                    dp[i - 1][3]  // 从冷冻期买入
                ) - prices[i]
            );
            // 状态1：保持卖出股票状态（可能是之前已卖出，或从冷冻期解除）
            dp[i][1] = Math.max(
                dp[i - 1][1], // 继续保持
                dp[i - 1][3]  // 冷冻期解除
            );
            // 状态2：今天卖出股票
            dp[i][2] = dp[i - 1][0] + prices[i];
            // 状态3：冷冻期（只有在前一天卖出时进入）
            dp[i][3] = dp[i - 1][2];
        }
        // 最终利润取最后一天的非持有状态中的最大值
        return Math.max(
            Math.max(dp[n - 1][1], dp[n - 1][2]), 
            dp[n - 1][3]
        );
    }
}

双维度问题

两个相互制约的维度需要分别处理。

135.分发糖果

巧妙

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] candies = new int[n];
        Arrays.fill(candies, 1); // 每人至少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]) {
                candies[i] = Math.max(candies[i], candies[i + 1] + 1);
            }
        }
        // 统计总糖果数
        int total = 0;
        for (int candy : candies) {
            total += candy;
        }
        return total;
    }
}

406.根据身高重建队列

本题有两个维度，h和k，看到这种题目一定要想如何确定一个维度，然后再按照另一个维度重新排列。
在按照身高从大到小排序后：
局部最优：优先按身高高的people的k来插入。插入操作过后的people满足队列属性
全局最优：最后都做完插入操作，整个队列满足题目队列属性

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people,(a,b)->{
            if(a[0]==b[0]) return a[1]-b[1];// a - b 是升序排列，故在a[0] == b[0]的狀況下，會根據k值升序排列
            return b[0]-a[0];   //b - a 是降序排列，在a[0] != b[0]，的狀況會根據h值降序排列
        });

        LinkedList<int[]> que=new LinkedList<>();

        for(int[] p:people){
            que.add(p[1],p);//Linkedlist.add(index, value)，會將value插入到指定index裡。 
        }
        return que.toArray(new int[people.length][]);
    }
}