贪心算法基础及leetcode例题

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int j=s.length-1;
        int sum = 0;

        for(int i=g.length-1;i>=0;i--){
            if(j>=0 && s[j]>=g[i]){
                sum++;
                j--;
            }
        }
        return sum;
    }
}

class Solution {
    public int wiggleMaxLength(int[] nums) {
    
        int prediff = 0;//考虑只有两个元素的时候，默认为0；为头元素制造一个平坡
        int curdiff = 0;
        int result = 1;//默认最右端有坡度
        //一个元素的时候
        if(nums.length == 0) return result;
        
        for(int i=0;i<nums.length-1;i++){//nums.length-1 因为最右端已经记录了

            curdiff = nums[i+1] - nums[i];
             
            if((prediff>=0 && curdiff <0) || (prediff<=0 && curdiff >0)){
                result++;
                prediff = curdiff;
            }
        //prediff = curdiff;
        }
        return result;
    }
}

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

        return sum;
    }
}

class Solution {
    public int candy(int[] ratings) {
        int sum = 0;
        int len = ratings.length;
        int[] candy = new int[len];
        

        candy[0]=1;


        for(int i=1;i<len;i++){
            if(ratings[i] > ratings[i-1]){
                candy[i] = candy[i-1] +1;
            }else{
                candy[i] =1;
            }
        }

        for(int i=len-2;i>=0;i--){
            if(ratings[i] > ratings[i+1]){
                candy[i] = Math.max(candy[i+1] +1,candy[i]);
            }
        }

        for(int i=0;i<len;i++){
            sum += candy[i];
        }

        return sum;
    }
}