3、贪心算法

一个算法问题使用暴力解法需要指数级时间，如果能使用动态规划消除重叠子问题，就可以降到多项式级别的时间，如果满足贪心选择性质，那么可以进一步降低时间复杂度，达到线性级别的。
每一步都做出一个局部最优的选择，最终的结果就是全局最优。注意，这是一种特殊性质，其实只有一小部分问题拥有这个性质。

比如你面前放着 100 张人民币，你只能拿十张，怎么才能拿最多的面额？显然每次选择剩下钞票中面值最大的一张，最后你的选择一定是最优的。

然而，大部分问题都明显不具有贪心选择性质。比如打斗地主，对手出对儿三，按照贪心策略，你应该出尽可能小的牌刚好压制住对方，但现实情况我们甚至可能会出王炸。这种情况就不能用贪心算法，而得使用动态规划解决。

题目列表：455、435、452、406、121、122、605、392、665、53、763

455. 分发饼干

题解思路：因为我们的饼干是有限的，孩子的胃口以及饼干的尺寸也是固定的。那么如何可以满足最多的小孩呢？给一个孩子的饼干应当尽量小并且又能满足该孩子，这样大饼干才能拿来给满足胃口比较大的孩子。

1、对孩子的胃口以及饼干的尺寸进行升序排序。
2、对于第一个孩子从第一个饼干开始分配，如果满足孩子的胃口，孩子索引+1，饼干索引+1，不满足则饼干索引+1.
3、直到遍历完所有的元素。

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        if (g == null || s == null)
            return 0;
        Arrays.sort(g);
        Arrays.sort(s);
        int index1 = 0;   //指向孩子胃口的索引
        int index2 = 0;   //指向饼干尺寸的索引
        while (index1 < g.length && index2 < s.length) {
            if(g[index1]<=s[index2]){
                index1++;
            }
            index2++;
        }
        return index1;//得到满足的小孩的个数
    }
}

关键点，对拥有的饼干数以及孩子的胃口进行排序，每次匹配都保证是试图通过最小尺寸的饼干来满足孩子

435. 无重叠区间

| 给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
注意:
1. 可以认为区间的终点总是大于它的起点。
1. 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。
示例 1:
输入: [ [1,2], [2,3], [3,4], [1,3] ] 输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。 | | —- |

题解思路1：贪心算法，题目描述中要求找到需要移除区间的最小数量，换而言之也就是获取到无重叠区间的最大数量。为了得到最大的数量，我们可以考虑每次选取都尽量选择最优值——区间的最右侧的端点应该最小，这样对于剩下的区间就有更多的选择的可能性

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0)
            return 0;
        //根据每个区间的最右侧端点进行排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[1] - interval2[1];
            }
        });
        int[] left = intervals[0];//获取第一个元素
        int res = 0;//存储结果
        for (int i = 1; i < intervals.length; i++) {
            int[] right = intervals[i];
            if (left[1] > right[0]) {
                //区间重合
                res++;
            } else {
                left = right;
            }
        }
        return res;
    }
}

注：这里不可以对interval[0]的起始位置进行升序排序。
举个例子：【1，5】、【2，3】、【3，4】如果加上对首位数字的排序的话结果为1，而只对右端数字排序的话结果为2。

题解思路2：状态dp表示「以区间 ii 为最后一个区间，可以选出的区间数量的最大值
dp[i] = Math.max(dp[i], dp[j] + 1);

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0)
            return 0;
        //根据每个区间的最右侧端点进行排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[0] - interval2[0];
            }
        });
        int[] dp = new int[intervals.length];
        Arrays.fill(dp,1);    
        int max = 1;
        for (int i = 1; i < intervals.length; i++) {
            for (int j = 0; j < i; j++) {
                if (intervals[i][0] >= intervals[j][1]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                    max = Math.max(max, dp[i]);
                }
            }
        }
        return (intervals.length) - max;
    }
}

注：1、max的设定值为1
2、排序

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

题解思路：其实也是求解重叠区间的问题。
也是计算不重叠的区间个数，不过和 Non-overlapping Intervals 的区别在于，[1, 2] 和 [2, 3] 在本题中算是重叠区间。

class Solution {
    public int findMinArrowShots(int[][] points) {
         if (points.length == 0)
                return 0;
            Arrays.sort(points, new Comparator<int[]>() {
                public int compare(int[] point1, int[] point2) {
                      return point1[1] < point2[1] ? -1 : 1;            *
                }
            });
            int n = points.length;
            int right = points[0][1];
            int ans = 1;
            for (int i = 1; i < n; i++) {
                if (points[i][0] <= right) {
                    continue;
                }
                ans++;
                right = points[i][1];
            }
            return ans;
    }
}

注意点：按照题435的操作，在用例[[-2147483646,-2147483645],[2147483646,2147483647]]中是跑不出来的（数据溢出的问题）所以需要将比较的程序更新为 return point1[1] < point2[1] ? -1 : 1;

406. 根据身高重建队列

题解思路：题目中主要给出了两个关键条件，一个是身高，一个是超过或等于该身高的个数。关键如何保证我们在排序的过程中，排序的结果能够满足个数这个条件。
1、将所有的数据按身高进行降序，按个数进行升序。
2、依次获取并插入到集合中。插入的位置就是人数的数值
注：为什么这样的方式是可行的呢？因为我们先操作的是身高高的people，保证后面插入的数值不会影响到前面插入的位置。

  public int[][] reconstructQueue(int[][] people) {
        if (people == null || people.length == 0) {
            return new int[0][0];
        }
        Arrays.sort(people, (a, b) -> (a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]));
        List<int[]> queue = new ArrayList<>();
        for (int[] p : people) {
            queue.add(p[1], p);
        }
        return queue.toArray(new int[0][]);        *
    }

关键点：最后的返回值为什么这样写？ 深入理解List的toArray(T[ ] a)方法在二维数组复制里的写法

121. 买卖股票的最佳时机

题解思路：根据题意我们要获取最小和最大的值，并且不能乱序。因此可以考虑遍历当前数组，获取到当前值前面的最小值即可得到在当前点卖出时可能收获的最大值

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

关键点：判断当前值是否小于前面的最小值，如果小于更新最小值，如果判断是否更新最大值

122. 买卖股票的最佳时机 II

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [7,1,5,3,6,4]
输出: 7
题解思路：为了达到更多的收益，每次都在价格下跌之前将股票卖掉

  public int maxProfit(int[] prices) {
        if (prices.length == 0)
            return 0;
        int max = 0;
        int inprice = prices[0];
        for (int i = 1; i < prices.length; i++) {
            if (inprice < prices[i]) {        //如果后一个价格大于上一个价格
                max += prices[i] - inprice; //收益增加
            }
            inprice = prices[i];            //将当前值更新为买入价格，注意这里不能使用else
        }
        return max;
    }

更加简单的思路

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

605. 种花问题

题解思路：获取满足左右条件为0的节点即可，关键点在于处理好边界条件

public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int len = flowerbed.length;

        for (int i = 0; i < len; i++) {
            if (flowerbed[i] == 1)
                continue;
            int pre = i == 0 ? 0 : flowerbed[i - 1];
            int next = i == len - 1 ? 0 : flowerbed[i + 1];
            if (pre == 0 && next == 0) {
                flowerbed[i] = 1;
                n--;
            }
        }
        return n <= 0 ? true : false;
    }

关键点：关于左右端点应该如何处理，避免出现角标越界的问题出现 int pre = i == 0 ? 0 : flowerbed[i - 1]; int next = i == len - 1 ? 0 : flowerbed[i + 1];

392. 判断子序列

题解思路1：考虑使用双指针的思想解决问题
1、创建两个指针分别指向s和t
2、根据不同的情况向右边移动
3、判断结果

 public boolean isSubsequence(String s, String t) {
        int slength = s.length();
        int tlength = t.length();
        int x1 = 0;//指向s的指针
        int x2 = 0;//指向t的指针

        while (x1 < slength && x2 < tlength) {
            if (s.charAt(x1) == t.charAt(x2)){
                x1++;    //如果存在相同的字符就移动
            }
            x2++;/每次比较都要移动
        }
        if (x1 == slength)
            return true;
        return false;
    }

错误写法：

while (s.charAt(x1) != t.charAt(x2)){
     x2++;//这样的写法必然存在角标越界的可能，同时也使得后面的处理更加的麻烦。
}

题解思路2：贪心算法
1、将字符串s转换为字符数组
2、依次在字符串t中寻找，注意起始索引要大于上一个索引

class Solution {
    public boolean isSubsequence(String s, String t) {
        int index = -1;
        for (char c : s.toCharArray()) {
            index = t.indexOf(c, index + 1);//每次寻找的范围都是从上一个结果的下一个开始
            if (index == -1) {
                return false;
            }
        }
        return true;
    }
}

int indexOf(String str, int startIndex)：从指定的索引处开始，返回第一次出现的指定子字符串在此字符串中的索引。 注意点：此处使用indexOf（String str）是会出现重复寻找到同一个值的情况出现

665. 非递减数列

审题：题目的意思为改变一个值的大小而不是可以移动值。那么在出现递减情况时就存在一个选择的问题，是应该改变前一个值还是改变当前值。为了保证后续的数字更加容易的递增，那么当前值就应该尽可能的小，所以应该改变上一个值。但是有一种特殊的情况，如果上上个值（i-2）大于当前值（i），那么当前值不得不改变以保证递增。还有就是关于改变后的值应该是多少的问题？我们应当保证改变后的值正好满足条件即可，这样可以为剩余的数值留有更多的可能性。

public boolean checkPossibility(int[] nums) {
        int cnt = 0;
        for (int i = 1; i < nums.length && cnt < 2; i++) {
            if (nums[i] >= nums[i - 1])
                continue;
            cnt++;
            if (i - 2 >= 0 && nums[i - 2] > nums[i])
                nums[i] = nums[i - 1];
            else
                nums[i - 1] = nums[i];
        }
        return cnt<=1;
    }

归纳：当nums【i】破坏了数组的单调递增时，即 nums[ i ] < nums[ i - 1 ] 时，为了让数组有序，需要判定改变哪一个数
1、当 i = 1 ，那么修改 num[ i- 1 ] ，不要动 nums[ i ] ，因为nums[i]后面的元素是啥我们还不知道呢，少动它为妙。
2、，当 i > 1 时，优先考虑把 nums[i - 1] 调小到 >= nums[i - 2] 并且 <= nums[i]。同样尽量不去修改 nums[i] ，理由同上。
3、当 i > 1 且 nums[i] < nums[i - 2] 时，我们无法调整 nums[i - 1] ，只能调整 nums[i] 到 nums[i - 1] 。

53. 最大子序和

题解思路1：贪心算法，如果sum>0，说明sum对于结果有增益效果，则sum保留并加上当前遍历数字，如果sum<0,说明sum对于结果没有增益效果，需要舍弃，则sum直接更新为当前遍历的数字

 public int maxSubArray(int[] nums) {
          if (nums == null || nums.length == 0)
            return 0;

        int preSum = nums[0];
        int maxSum = preSum;

        for (int i = 1; i < nums.length; i++) {
            preSum =preSum>0 ? preSum + nums[i] : nums[i];
            maxSum = Math.max(maxSum, preSum);
        }
        return maxSum;
    }

题解思路2：动态规划思想（dp[i] = max(dp[i-1] + nums[i], num[i]);）

 public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int max = dp[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            if (max < dp[i])
                max = dp[i];
        }
        return max;
    }

763. 划分字母区间

题解思路：
1、获取每个元素最后出现的索引位置
2、如果在这个索引范围内出现新的元素，就更新最远端的位置。

class Solution {
    public List<Integer> partitionLabels(String S) {
        int[] last = new int[26];
        int length = S.length();
        for (int i = 0; i < length; i++) {
            last[S.charAt(i) - 'a'] = i;
        }
        List<Integer> partition = new ArrayList<Integer>();
        int start = 0, end = 0;
        for (int i = 0; i < length; i++) {
            end = Math.max(end, last[S.charAt(i) - 'a']);
            if (i == end) {
                partition.add(end - start + 1);
                start = end + 1;
            }
        }
        return partition;
    }
}

55. 跳跃游戏

自己的思路：回溯

public boolean canJump(int[] nums) {
        boolean res = backtrace(nums, 0, 0);
        return res;
    }

    public boolean backtrace(int[] nums, int index, int length) {
        if (index > nums.length - 1)
            return false;
        if (length == nums.length - 1) {
            return true;
        }

        //当前索引可以跳的步数
        int num = nums[index];
        for (int i = num; i > 0; i--) {
            if (nums.length - length < i) {
                continue;
            }
            length += i;
            if (backtrace(nums, index + i, length))
                return true;
            length -= i;
        }
        return false;
    }

结果超时

题解思路：贪心算法
依次遍历数组中的每一个位置，并实时维护最远可以到达的位置。对于当前遍历到的位置 xx，如果它最远可以到达的位置的范围内，那么我们就可以从起点通过若干次跳跃到达该位置，因此我们可以用 x + \textit{nums}[x]x+nums[x] 更新 最远可以到达的位置。

class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        int rightmost = 0;
        for (int i = 0; i < n; ++i) {
            if (i <= rightmost) {        //这一步很关键


                if (rightmost >= n - 1) {
                    return true;
                }
            }
        }
        return false;
    }
}

注：在for循环中进行了一次判定，当前的索引位置是不是可达的。

621. 任务调度器

难度中等656
给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态。
然而，两个 相同种类 的任务之间必须有长度为整数 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。
你需要计算完成所有任务所需要的 最短时间 。

示例 1：
输入：tasks = [“A”,”A”,”A”,”B”,”B”,”B”], n = 2
输出：8
解释：A -> B -> (待命) -> A -> B -> (待命) -> A -> B
在本示例中，两个相同类型任务之间必须间隔长度为 n = 2 的冷却时间，而执行一个任务只需要一个单位时间，所以中间出现了（待命）状态。

581. 最短无序连续子数组

题解思路：遍历nums数组中的每一个元素nums［ｉ］。对于每一个元素，尝试找到它在正确顺序数组中的位置，即将它与每一个满足　ｉ＜ｊ＜ｎ的nums［ｊ］做比较，这里ｎ是ｎｕｍｓ数组的长度。

如果存在nums［ｊ］比ｎｕｍｓ［ｊ］都不在排序后数组中的正确位置。标记这两个元素在原数组中的位置ｉ和ｊ。这两个元素标记着目前无需数组的边界。
因此我们需要找到最左边的非正确的索引以及最右边的非正确的索引位置。

题解思路１：双重for循环

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int l=nums.length;int r=0;
        for(int i=0;i<nums.length-1;i++){
            for(int j=i+1;j<nums.length;j++){
                if(nums[j]<nums[i]){
                    r=Math.max(r,j);
                    l=Math.min(l,i);
                }
            }
        }
        return r-l<0?0:r-l+1;
    }
}

题解思路２：单循环，同时从前往后和从后往前遍历，分别得到排序数组的右边界和左边界
寻找右边界：
从前往后遍历，用max记录遍历过的最大值，如果max大于当前的ｎｕｍｓ［ｉ］，说明ｎｕｍｓ［ｉ］的位置不正确，属于需要排序的数组，因此将右边界的位置更新为ｉ，然后更新ｍａｘ；这样最终可以找到需要排序的数组的右边界，右边界之后的元素都大于max

寻找左边界：
从后往前遍历的过程中，用min记录遍历过的最小值，如果min小于当前的nums[ｊ]，说明nums[j]的位置不正确，应该属于需要排序的数组，因此将左边界更新为j，然后更新min；这样最终可以找到需要排序的数组的左边界，左边界之前的元素都小于min；
（从前往后遍历和从后往前遍历两个过程可以分两次循环完成，也可以放一起完成，这样的话就有：j=len-i-1）

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int len = nums.length;
        int max = nums[0];
        int min = nums[len-1];
        int l = 0, r = -1;
        for(int i=0;i<len;i++){
            if(max>nums[i]){
                r = i;
            }else{
                max = nums[i];
            }
            if(min<nums[len-i-1]){
                l = len-i-1;
            }else{
                min = nums[len-i-1];
            }
        }
        return r-l+1;
    }
}

题解思路3：使用栈
我们需要要找到无序子数组中最大元素和最下元素分别对应的正确位置，来求得想要的无序子数组的边界。
为了达到这个目的，可以使用栈。从头遍历nums数组，遇到的数字大小一直是升序的，就可以不断的将对应的下标压栈。这么做的目的是因为在当前遍历的环境下都处于正确的位置。但是当出现某个元素比前一个元素的值要大的时候，也就是出现nums[ j ]不处于正确的位置。

为了找到nums[ j ]的正确位置，就要不断的弹出元素，直到满足栈顶元素比nums[ j ]小。假设栈顶元素的下标位置为k，那么就可以知道nums[ j ]的正确的位置应该是处于k+1的。

重复这个过程遍历完全部的数值，就可以找到最小的k，也就是无序子数组的左边界

类似的，逆序遍历一遍nums数组来找到无序子数组的右边界。

注：其实本质上还是在求最左边界和最优边界

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        Stack<Integer> stack=new Stack<>();

        int l=nums.length,r=0;
        for(int i=0;i<nums.length;i++){
            while(!stack.isEmpty()&&nums[stack.peek()]>nums[i])
                l=Math.min(l,stack.pop());
            stack.push(i);
        }
        stack.clear();

        for(int i=nums.length-1;i>=0;i--){
             while(!stack.isEmpty()&&nums[stack.peek()]<nums[i])
                r=Math.max(r,stack.pop());
            stack.push(i);
        }

        return r-l>0?r-l+1:0;
    }
}