分糖果问题

public class Solution {
    /**
     * 给定一个数组 arrarr 代表得分数组，请返回最少需要多少糖果。
     *
     * pick candy
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int candy (int[] arr) {
        int candy[] = new int[arr.length];
        for (int i = 0; i < candy.length; i++) {
            candy[i] = 1;
        }
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > arr[i - 1]) {
                candy[i] = candy[i - 1] + 1;
            }
        }
        int count = 0 ;
        for (int i = arr.length - 1; i > 0; i--) {
            if (arr[i - 1] > arr[i] && candy[i - 1] <= candy[i]) {
                candy[i - 1]  = candy[i] + 1;
            }
            count += candy[i];
        }
        return count += candy[0];
    }
    
}

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * pick candy
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int candy (int[] arr) {
        // 左遍历一次，再右遍历一次
        if(arr.length<=1) return 1;
        int[] nums=new int[arr.length];//辅助数组，初始化为1
        for(int i=0;i<nums.length;i++){
            nums[i]=1;
        }
        //左遍历   i-1,i
        for(int i=1;i<arr.length;i++){//i从1开始
            if(arr[i]>arr[i-1]){   //如果原数组递增，那就给num[i]糖果+1
                nums[i]=nums[i-1]+1;
            }
        }
        int ans=nums[arr.length-1];
        //右遍历   i,i+1
        for(int i=arr.length-2;i>=0;i--){
            if(arr[i]>arr[i+1]&&nums[i]<=nums[i+1]){
                nums[i]=nums[i+1]+1;
            }
            ans=ans+nums[i];//ans原来是个空数组   使用了两次辅助数组nums[i]
        }
        return ans;
    }

import java.util.*;


public class Solution {
    /**
     * pick candy
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int candy (int[] arr) {
        // write code here
        int[] scores = new int[arr.length];
        int cd = 0;
        for (int i = 0; i < arr.length ; i++) {
            scores[i] = 1;
        }
       
                for (int i = arr.length - 1 ; i > 0; i--) {
            if (arr[i] < arr[i - 1]) {
                scores[i - 1] = scores[i] + 1;
            }
           

        }
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] < arr[i + 1] && scores[i+1] <= scores[i]) {
                scores[i + 1] = scores[i] + 1;
            }
           

        }

        for (int i = 0; i < arr.length; i++) {
            cd += scores[i];
            System.out.println(scores[i]);
        }
        return cd;
    }
}

import java.util.*;


public class Solution {
    public int candy (int[] arr) {
        // write code here
        int n = arr.length;
        int[] left = new int[n];
        int[] right = new int[n];
        for (int i = 1; i < n; i++) {
            //左侧单调递增区间
            if (arr[i] > arr[i - 1]) left[i] = left[i - 1] + 1;
        }
        for (int i = n - 2; i >= 0; i--) {
            //右侧单调递减区间
            if (arr[i] > arr[i + 1]) right[i] = right[i + 1] + 1;
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans += Math.max(left[i], right[i]) + 1;
        }
        return ans;
    }
}

import java.util.*;


public class Solution {
    /**
     * pick candy
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int candy (int[] arr) {
        // write code here
        int[] left=new int[arr.length];
        int[] right=new int[arr.length];
        int candy=0;
        
        left[0]=1;
        right[arr.length-1]=1;
        
        for(int i=1;i<=arr.length-1;i++){
            if(arr[i]>arr[i-1]){
                left[i]=left[i-1]+1;
            }else{
                left[i]=1;
            }
        }
        for(int i=arr.length-2;i>=0;i--){
            if(arr[i]>arr[i+1]){
                right[i]=right[i+1]+1;
            }else{
                right[i]=1;
            }
        }
        for(int i=0;i<=arr.length-1;i++){
            candy=candy+Math.max(left[i],right[i]);
        }
        return candy;
    }
}

import java.util.*;


public class Solution {
    /**
     * pick candy
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int candy (int[] arr) {
        // write code here
        int[] dp = new int[arr.length];
        Arrays.fill(dp, 1);
        int res = 0;

        for (int i = 1; i < arr.length; i ++) {
            if (arr[i] > arr[i - 1]) dp[i] = dp[i - 1] + 1;
        }

        res = dp[arr.length - 1];
        for (int i = arr.length - 2; i >= 0; i--) {
            if (arr[i] > arr[i + 1] && dp[i] <= dp[i + 1]) dp[i] = dp[i + 1] + 1;
            res += dp[i];
        }

        return res;
    }
}

题解: 要想分出最少的糖果，利用贪心思想，肯定是相邻位置没有增加的情况下，大家都分到1，相邻位置有增加的情况下，分到糖果数加1就好。
什么情况下会增加糖果，相邻位置有得分差异，可能是递增可能是递减，如果是递增的话，糖果依次加1，如果是递减糖果依次减1？
最后不符合最小，原因是序列中的两个任意两个元素之间必然是递增，递减，相等等三种情况，不管多长的序列都可以细分成任意两个元素的子问题
想象序列前半部分递增，后半部分递减，如果后半部分比前半部分短，最后减完是不是最后一个元素是不是大于1，所以不能得到最小值
如果是多个递增递减的序列的组合形成的序列，那么其中任意两个不等长子序列都会产生这个情况，所以诞生了下面的思路： 1.先从左到右，大于的就+1，小于的不管，然后从后向前遍历，前面的大于后面的就+1，假设序列只有递增递减两部分，如1232或者12321或者2321 12321肯定直接适用，前者因为3处于返回的时候的递增，所以应该更新为1个糖果+1=2，但是这样就把当时原来递增的数量给破坏了，所以由于前后子序列的不确定性
我们直接取max（原来的递增时数量，递减返回时的后置元素+1），谁大取谁，因为这样一定能满足大于两边的情况
import java.util.*;
public class Solution {
    /**
     * pick candy
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int candy (int[] arr) {
        int length = arr.length;
        int count = 0;
        int num[] = new int[length];
        Arrays.fill(num,1);
        for(int i=1;i<length;i++){
            if(arr[i]>arr[i-1]){
                num[i] = num[i-1]+1;
            }
        }
        for(int i = length-1;i>0;i--){
            if(arr[i]<arr[i-1]){
                num[i-1] = Math.max(num[i-1],num[i]+1);
            }
        }
        for(int i :num){
            count+=i;
        }
        return count;

    }
}

public class Solution {

    public int candy (int[] arr) {
        if (arr==null || arr.length==0) return 0;
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            ++res[i];
            if (i>0 && arr[i]>arr[i-1]) {
                res[i] = res[i-1]+1;
            }
        }
        int sum = 0;
        for (int i = arr.length-1; i >=0 ; i--) {
            if (i<arr.length-1 && arr[i]>arr[i+1] && res[i]<=res[i+1]) {
                res[i] = res[i+1]+1;
            }
            sum = sum + res[i];
        }
        return sum;
    }
}

思路（贪心策略）：
注意：若两个孩子得分相同，分配糖果无限制，即不需要保证分数相同（相邻与否），得到的糖果数相同
1、先创建一个长度为arr.length，元素都为1的数组
2、从左往右看：索引值从 0 到length-2，看arr[i] 与 arr[i+1]的关系，如果arr[i]<arr[i+1]，则 i+1位置 上的糖果比 i位置 多给一个，即candy[i+1]=candy[i]+1;
3、从右往左看：索引值从 length-1 到 1，看arr[i] 与 arr[i-1]的关系，如果arr[i-1]>arr[i]，则 i-1位置 上的糖果要保证比 i位置 上的多，即candy[i-1]=Math.max(candy[i-1],candy[i]+1); 因为candy[i-1]可能已经在“从左往右看”的时候被再次赋值过，这个值有可能比candy[i]大，因此需要进行比较，选出最大的，这样可以保证糖果比左右的都要多，例如：分数序列123451，5就比1+1大
总结：从左往右，保证右边比左边大的时候，糖果数也大；从右往左，保证右边比左边大或相等的情况下，糖果数符合要求

import java.util.*;
public class Solution {
    public int candy (int[] arr) {
        // write code here
        int len = arr.length;
        if(len==0) return 0;
        if(len==1) return 1;
        int[] candy = new int[len];
        for(int i=0;i<len;i++){
            candy[i]=1;
        }
        for(int i=1;i<len;i++){
            if(arr[i]>arr[i-1]){
                candy[i]=candy[i-1]+1;
            }
        }
        for(int i=len-1;i>0;i--){
            if(arr[i-1]>arr[i]){
                candy[i-1] = Math.max(candy[i-1],candy[i]+1);
            }
        }
        int res=0;
        for(int i=0;i<len;i++){
            res+=candy[i];
        }
        return res;
    }
}

import java.util.*;


public class Solution {

    public int candy (int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int n = arr.length;
        int[] nums = new int[n];
        // 先分一个
        Arrays.fill(nums, 1);
        // 得分比前一个多，需要保证糖果数量也比前一个多
        for (int i = 1; i < n; i++) {
            if (arr[i] > arr[i - 1]) {
                nums[i] = nums[i - 1] + 1;
            }
        }
        // 得分比后一个多，需要保证糖果数量也比后一个多
        for (int i = n - 2; i >= 0; i--) {
            if (arr[i] > arr[i + 1]) {
                if (nums[i] <= nums[i + 1]) {
                    nums[i] =  nums[i + 1] + 1;
                }
            }
        }
        int sum = 0;
        for (int num:nums) {
            sum += num;
        }
        return sum;
    }
}