6_贪心.md

贪心

1、连续子数组的最大和（45）

连续子数组的最大和

//思路：
//贪心策略：遍历数组，到当前位置，上次保留的最大值如果为负数就要刷新一次，
// 即 curSum<=0时，当即果断丢弃，因为只会越加越小，刷新为当前值；
// 如果为正数，继续累加。

public int FindGreatestSumOfSubArray(int[] array) {
    if (array == null || array.length == 0){
        return 0;
    }
    int curSum = 0;
    int res= Integer.MIN_VALUE;
    for(int i=0;i<array.length;i++){
        if(curSum<=0){
            curSum = array[i];
        }else{
            curSum += array[i];
        }
        res = Math.max(res,curSum);
    }
    return res;
}

2、买卖股票的时机

买卖股票的时机

//思路：
// 贪心策略
// 假设第 i 轮进行卖出操作，买入操作价格应该在 i 之前并且价格最低。
public int maxProfit(int[] prices) {
    int n = prices.length;
    if(n==0 || n==1){
        return 0;
    }
    int minValue = prices[0];
    //初始时，不进行交易，当然收益为0
    int maxProfit  = 0 ;
    for(int i=1;i<n;i++){
        minValue = Math.min(minValue,prices[i]); //在 i 轮卖出前，以最低价格买入
        maxProfit = Math.max(maxProfit,prices[i]-minValue); //贪心策略：每轮都买出
    }
    return maxProfit;
}

3、合并区间

合并区间

public int[][] merge(int[][] intervals) {
    int m=intervals.length;
    if(m==0){
        return new int[][]{};
    }
    if(m==1){ //只有1个区间，则不需要合并
        return intervals;
    }

    // list 存储原始的区间
    List<Interval> list=new ArrayList<>();
    for(int i=0;i<m;i++){
        list.add(new Interval(intervals[i][0],intervals[i][1]));
    }
    Collections.sort(list, new Comparator<Interval>() { //按照其实位置进行排序
        @Override
        public int compare(Interval o1, Interval o2) {
            int num=o1.start-o2.start;
            int num2=(num==0)?(o1.end-o2.end):num;
            return num2;
        }
    });

    ArrayList<Interval> res=new ArrayList<>();
    Interval cur=list.get(0);
    for(int i=1;i<m;i++){
        if(cur.end>=list.get(i).start){ //存在区间交叉
            //区间进行合并
            cur.end=Math.max(cur.end,list.get(i).end);
        }else{ //不存在交叉
            res.add(cur);
            cur=list.get(i);
        }
        if(i==m-1){
            res.add(cur);
        }
    }

    int n=res.size();
    int[][] matrix=new int[n][2];
    for(int i=0;i<n;i++){
        Interval tmp=res.get(i);
        matrix[i][0]=tmp.start;
        matrix[i][1]=tmp.end;
    }
    return matrix;
}

private class Interval{
    public int start;
    public int end;
    public Interval(int start,int end){
        this.start=start;
        this.end=end;
    }
}

4、分发饼干

分发饼干

5、无重叠区间

无重叠区间

6、救生艇

救生艇

7、用最少数量的箭引爆气球

用最少数量的箭引爆气球

8、汇总区间

汇总区间