BM95 分糖果问题

一群孩子做游戏，现在请你根据游戏得分来发糖果，要求如下：

1. 每个孩子不管得分多少，起码分到一个糖果。

2. 任意两个相邻的孩子之间，得分较多的孩子必须拿多一些糖果。(若相同则无此限制)

给定一个数组 arrarr 代表得分数组，请返回最少需要多少糖果。

要求: 时间复杂度为 O(n)O(n) 空间复杂度为 O(n)O(n)

每个人至少一个。

从左向右遍历一次，满足右侧的人。（类似于传声筒，从左向右遍历时，只关心是不是比自己左侧的高）

从右向左遍历一次，满足左侧的人。（类似于传声筒，从右向左遍历时，只关心是不是比自己右侧的高）

    public int candy (int[] arr) {
        // write code here
        int[] result = new int[arr.length];
        
        // 每人至少一个
        for (int i = 0 ; i < result.length; i++){
            result[i] = 1;
        }
        
        // 右边的比左边的分值高，得多分一个
        for (int i = 1 ; i < arr.length; i++){
            if (arr[i] > arr[i-1]){
                result[i] = result[i-1] + 1;
            }
        }
        
        // 左边的比右边的分值高
        for (int i = arr.length - 1; i > 0; i--){
            if (arr[i - 1] > arr[i]){
                result[i - 1] = result[i-1] < result[i] + 1 ? result[i] + 1 : result[i-1];
            }
        }
        
        int sum = 0;
        for (int i = 0 ; i < result.length; i++){
            sum += result[i];
        }
        
        return sum;
    }

注：从右向左遍历时，需要注意左侧分得的糖果已经比右侧大的可能性。