题解 | #分糖果问题#

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 = candy3(arr);
        System.out.println("res = " + res);
    }

    public static int candy(int[] arr) {
        // write code here
        int length = arr.length;
        int res = length;
        // 降序flag
        int descFlag = 0;
        // 升序flag
        int ascFlag = 0;
        // 相等flag
        int euityFlag = 0;
        for (int i = 1; i < length; i++) {
            // 降序会改变flag，升序重置flag
            if (arr[i] < arr[i - 1]) {
                if (euityFlag != 0) {
                    if (ascFlag != 0) {
                        // 如果是先升后降则相当于是峰值
                        res += euityFlag;
                        ascFlag = 0;
                        continue;
                    } else {
                        descFlag += euityFlag;
                    }
                    euityFlag = 0;
                }
                ascFlag = 0;

                if (i == 1 || (i >= 2 && arr[i - 1] <= arr[i - 2])) {
                    descFlag++;
                }
                res += descFlag;
            } else if (arr[i] > arr[i - 1]) {
                descFlag = 0;
                if (euityFlag != 0) {
                    if (ascFlag != 0) {
                        res += euityFlag;
                    }
                    euityFlag = 0;
                }
                ascFlag++;
                res += ascFlag;
            } else {
                // 相等
                euityFlag++;
            }
        }
        // 最后是递增且相同的趋势
        if (euityFlag != 0 && ascFlag != 0) {
            res += euityFlag;
            euityFlag = 0;
        }
        return res;
    }

    public static int candy2(int[] arr) {
        int up = 0, down = 0, peak = 1, res = 1;
        for (int i = 1; i < arr.length; i++) {
            res++;
            if (arr[i] > arr[i - 1]) {
                up++;
                res += up;
                down = 0;
                peak = up + 1;
            } else if (arr[i] == arr[i - 1]) {
                up = 0;
                down = 0;
                peak = 1;
            } else {
                up = 0;
                res += down;
                down++;
                if (down >= peak)
                    res++;
            }
        }
        return 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;
    }

}