public class _135 {
    static class Solution1 {
        public int candy(int[] ratings) {
            //利用动态规划来计算
            //i位置，左侧存在连续的rating数小于它，右侧连续的rating小于它
            int[][] dp = new int[2][ratings.length];
            for (int i = 1; i < dp[0].length; i++) {
                if (ratings[i] > ratings[i - 1]) {
                    dp[0][i] = dp[0][i - 1] + 1;
                }
            }
            for (int j = dp[1].length - 2; j >= 0; j--) {
                if (ratings[j] > ratings[j + 1]) {
                    dp[1][j] = dp[1][j + 1] + 1;
                }
            }
            int sum = 0;
            for (int i = 0; i < dp[0].length; i++) {
                sum += Math.max(dp[0][i], dp[1][i]);
            }
            return sum += dp[0].length;

        }
    }

    static class Solution2 {
        public int candy(int[] ratings) {
            //discuss上 O(1)空间复杂度
            //如何消除额外的空间
            //某个i 从它的左侧向左移动连续小于它的rating 为 x
            //从它右侧移动连续小于它的数为 y,
            //然后 for i --> ratings.length sum(max(xi,yi));
            //如何通过一次遍历来完成？
            // up 统计连续增加的数量，down统计连续减少的次数
            //peak记录当前连续增加的最大值
            int up = 0, down = 0, peak = 0, res = 1;
            for (int i = 1; i < ratings.length; i++) {
                if (ratings[i] > ratings[i - 1]) {
                    res += ++up + 1;
                    peak = up;
                    down = 0;
                } else if (ratings[i] < ratings[i - 1]) {
                    ++down;
                    //该怎么证明这是正确的呢？它可以保证最终的和不变
                    res += 1 + down + (down > peak ? 0 : -1);
                    up = 0;
                } else {
                    peak = up = down = 0;
                    res++;
                }
            }
            return res;

        }
    }

    static class Solution3{
        public int candy(int[] ratings) {
            //找极小值,然后分别从2侧扫描，区最大值，和动态规划思路基本一致
            if(ratings.length < 2) return 1;
            int[] res = new int[ratings.length];
            for(int i = 0;i < ratings.length;i++){
                if(i == 0) {
                    if(ratings[i] <= ratings[i+1])res[i] = 1;
                }else if (i == ratings.length -1){
                    if(ratings[i-1] >= ratings[i]) res[i] = 1;
                }else if(ratings[i] <= ratings[i-1] && ratings[i] <= ratings[i+1]){
                    res[i] = 1;
                }
            }
            for(int i = 1;i < res.length;i++){
                if(ratings[i] > ratings[i-1] && res[i-1] > 0 ){
                    res[i] = Math.max(res[i-1] + 1,res[i]);
                }
            }
            for(int i = res.length -2;i >=0;i--){
                if(ratings[i] > ratings[i+1] && res[i+1] > 0){
                    res[i] = Math.max(res[i+1] + 1,res[i]);
                }
            }

            int sum = 0;
            for(int i = 0;i < res.length;i++){
                sum += res[i];
            }
            return sum;
        }
    }
}