题解 | #分糖果问题#

package com.hhdd.贪心;

/**
 * 不会做
 *
 * @Author huanghedidi
 * @Date 2022/8/11 22:54
 */
public class 分糖果问题 {

    public static void main(String[] args) {
//        int[] arr = {1, 4, 2, 7, 9};
//        int[] arr = {10,4,10,10,4};
        // 46才对
        int[] arr = {8, 9, 8, 7, 6, 5, 4, 3, 2, 1};
        int res = candy4(arr);
        System.out.println("res = " + res);
    }

    public static int candy3(int[] arr) {
        // write code here
        int length = arr.length;
        int res = length;
        // 降序flag
        int descFlag = 0;
        // 升序flag
        int ascFlag = 0;
        // 记录上升的极值点
        int peak = 0;
        for (int i = 1; i < length; i++) {
            // 降序会改变flag，升序重置flag
            if (arr[i] < arr[i - 1]) {
                // 降序会遇到极大值问题 如果升序的坡度比降序来的高则不需要改变极值点的值
                // 否则需要++
                // 不是很好理解
                ascFlag = 0;
                descFlag++;
                res += descFlag - 1;
                if (descFlag > peak) {
                    res++;
                }
            } else if (arr[i] > arr[i - 1]) {
                descFlag = 0;
                ascFlag++;
                peak = ascFlag;
                res += ascFlag;
            } else {
                // 相等
                ascFlag = 0;
                descFlag = 0;
                peak = 0;
            }
        }
        return res;
    }

    /**
     * 前后遍历两次的方法
     *
     * @param arr
     * @return
     */
    public static int candy4(int[] arr) {
        int[] res = new int[arr.length];
        for (int i = 0; i < res.length; i++) {
            res[i] = 1;
        }
        // 从左往右，如果右边的分数高，则在左边的基础上加1
        // 如果右边分数低 则是1
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > arr[i - 1]) {
                res[i] = res[i - 1] + 1;
            }
        }
        // 从右往左 如果左边分数高，则max(右边的基础上+1,原值)
        for (int i = arr.length - 2; i >= 0; i--) {
            if (arr[i] > arr[i + 1]) {
                res[i] = Math.max(res[i + 1] + 1, res[i]);
            }
        }
        int ans = 0;
        for (int i = 0; i < res.length; i++) {
            ans += res[i];
        }
        return ans;
    }


}