分糖果问题

[美团]
链接：https://www.nowcoder.com/questionTerminal/76039109dd0b47e994c08d8319faa352
来源：牛客网

一群孩子做游戏，现在请你根据游戏得分来发糖果，要求如下：
1. 每个孩子不管得分多少，起码分到一个糖果。
2. 任意两个相邻的孩子之间，得分较多的孩子必须拿多一些糖果。(若相同则无此限制)
给定一个数组arr代表得分数组，请返回最少需要多少糖果。
[要求]
时间复杂度为On, 空间复杂度为O1

示例1

输入

[1,1,2]

输出

4

说明

最优分配方案为1, 1，2

解答：正反序各来一次

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