主要思路

本题有一个贪心点，即：针对局部最小值位置，只需要分一颗糖果即可。

什么是局部最小值?

如果i位置是局部最小值，则有arr[i] < arr[i+1]且arr[i] < arr[i-1]。如果是第一个位置，则只需要满足arr[i] < arr[i+1]，如果是最后一个位置，则只需要满足arr[i] < arr[i-1]。

如果某个位置j不是局部最小值所在位置，则有如下两种情况

第一种情况，如果arr[j] > arr[j-1]，则j位置分的糖果数量的一种可能性是是j-1位置分得糖果的数量加1，

第二种情况，如果arr[j] < arr[j+1]，则j位置分的糖果数量的另外一个可能性是j+1位置分得糖果的数量加1，

上述两种情况取相对大的一个，即为arr[j]上需要分的糖果数量。

如何优雅表示两种情况呢？我们可以设置两个数组，长度和原始数组一样，其中

        int[] left = new int[n]; left[0] = 1;for (int i = 1; i < n; i++) {left[i] = arr[i] > arr[i - 1] ? left[i - 1] + 1 : 1;}

表示arr[j]只考虑和前一个数arr[j-1]得到的结果数组。

        int[] right = new int[n];right[n - 1] = 1;for (int i = n - 2; i >= 0; i--) {right[i] = arr[i] > arr[i + 1] ? right[i + 1] + 1 : 1;}

表示arr[j]只考虑和后一个数arr[j+1]得到的结果数组。

最后，每个位置取最大值累加即可

        int sum = 0;for (int i = 0; i < n; i++) {sum += Math.max(left[i], right[i]);}

完整代码如下

    public static int candy(int[] arr) {if (null == arr || arr.length == 0) {return 0;}int n = arr.length;int[] left = new int[n];int[] right = new int[n];left[0] = 1;for (int i = 1; i < n; i++) {left[i] = arr[i] > arr[i - 1] ? left[i - 1] + 1 : 1;}right[n - 1] = 1;for (int i = n - 2; i >= 0; i--) {right[i] = arr[i] > arr[i + 1] ? right[i + 1] + 1 : 1;}int sum = 0;for (int i = 0; i < n; i++) {sum += Math.max(left[i], right[i]);}return sum;}

本题和上一问唯一的区别就是，针对相等分数的同学，糖果必须一致，我们可以根据上述代码稍作改动即可, 见如下注释部分。

        int[] left = new int[n];int[] right = new int[n];left[0] = 1;for (int i = 1; i < n; i++) {if (arr[i] > arr[i - 1]) {left[i] = left[i - 1] + 1;} else if (arr[i] == arr[i - 1]) {// 在相等的情况下，保留前一个位置的值left[i] = left[i - 1];} else {left[i] = 1;}}right[n - 1] = 1;for (int i = n - 2; i >= 0; i--) {if (arr[i] > arr[i + 1]) {right[i] = right[i + 1] + 1;} else if (arr[i] == arr[i + 1]) {// 在相等的情况下，保留后一个位置的值right[i] = right[i + 1];} else {right[i] = 1;}}

完整代码如下

import java.util.Scanner;// 链接：https://www.nowcoder.com/questionTerminal/de342201576e44548685b6c10734716e
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int[] arr = new int[n];for (int i = 0; i < n; i++) {arr[i] = in.nextInt();}System.out.println(candy(arr));in.close();}// 进阶：相等分数糖果一定要相等public static int candy(int[] arr) {int n = arr.length;int[] left = new int[n];int[] right = new int[n];left[0] = 1;for (int i = 1; i < n; i++) {if (arr[i] > arr[i - 1]) {left[i] = left[i - 1] + 1;} else if (arr[i] == arr[i - 1]) {left[i] = left[i - 1];} else {left[i] = 1;}}right[n - 1] = 1;for (int i = n - 2; i >= 0; i--) {if (arr[i] > arr[i + 1]) {right[i] = right[i + 1] + 1;} else if (arr[i] == arr[i + 1]) {right[i] = right[i + 1];} else {right[i] = 1;}}int sum = 0;for (int i = 0; i < n; i++) {sum += Math.max(left[i], right[i]);}return sum;}
}