java 数据结构和算法刷新 -----LeetCode135。分发糖果

java数据结构与算法刷题目录（剑指Offer、LeetCode、ACM）-----主目录-----持续更新(进不去说明我没写完)：https://blog.****.net/grd_java/article/details/123063846

1. 左右遍历

解题思路：时间复杂度O($n$)，遍历两次数组，空间复杂度O($n$)，需要记录左遍历一次后的同学手里的糖

1. 先从左到右，依次给孩子们发糖，如果当前孩子分数比前一个高，就比前一个孩子多发一块糖，否则只给一块糖
2. 此时老师们发现当前发的糖，不满足校方的要求，所以从右到左，想用right块糖和同学们手里的糖交换
3. 如果当前孩子分数，比右边孩子的高，就以比右边孩子多发一块的数量right试图和当前孩子交换。如果比右边孩子的低，就只发一块试图交换
4. 孩子很聪明，如果老师给的right块糖 < 自己当前持有的，孩子就不交换

代码

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] left = new int[n];//先从左到右处理一次，将处理结果保存起来
        //注意，处理左到右时，不要统计糖果总数
        for (int i = 0; i < n; i++) {
            if (i > 0 && ratings[i] > ratings[i - 1]) {//如果当前同学分数 > 前一个同学(左边同学)
                left[i] = left[i - 1] + 1;//比前一个同学多分一块糖果
            } else {//如果< = 前一个同学，先分配一块糖
                left[i] = 1;
            }
        }
        int right = 0, ret = 0;//right是通过给当前同学几块糖来交换它手里现在持有的糖（同学很聪明，只有right比自己手里的多才换），ret是糖果总数
        //这里才需要统计糖果总数
        for (int i = n - 1; i >= 0; i--) {
            if (i < n - 1 && ratings[i] > ratings[i + 1]) {//如果当前同学 > 后面同学（右边同学）
                right++;//如果它 "连续" > 若干个右边的同学, 这若干个连续的右边的同学有几个，就给他分几块糖
            } else {
                right = 1;//当不在连续时，默认用一块糖换他手里的糖，看它换不换
            }
            //如果当前同学本身已有糖果 > right（我们现在想和它交换的糖果数量），他就不换
            //如果right>left[i](当前同学已有糖果)，同学选择用自己已有的糖，换取right块糖
            ret += Math.max(left[i], right);//然后将自己持有的糖统计到ret中
        }
        return ret;
    }
}

2. 进阶：常数空间遍历，升序降序分治法

升序降序分治法:就是将整个数组按照顺序，分成升序序列和降序序列。不再以单个元素为单位判断，而是以一个子序列为单位进行逻辑判断处理

1. 这种算法，整个数组的第一个元素很关键
2. 我们必须规定数组第一个元素是算作升序还是降序
3. 因为升序的最后一个元素是最大的，降序的第一个元素是最大的。例如[1,2,3],[3,2,1],这两个序列，第一个是升序，第二个是降序，一个最大值在最后，一个最大值在最前面。
4. 而这种思想怎么用到这道题呢？看下面的解题思路吧。

解题思路：时间复杂度O($n$)，空间复杂度O($1$)

1. 将孩子所持有的分数的分布，看成两种形态，升序序列和降序序列
2. 则每一个升序序列结束，必然紧跟一个降序序列，或者后面没有序列，反过来也一样，每一个降序序列后面，如果有其它序列，必然是一个升序序列
3. 而我们要尽可能少分配糖果。

1. 对于升序序列，第一个孩子分1块，后面每一个人比前一个人多分一块，构成升序，等差数列(1,2,3,4,5…)
2. 对于降序序列，最后一个孩子分1块，前面每一个比后面一个人多分一块，构成降序，等差数列(…5,4,3,2,1)

3. 每个升序序列的最后一个孩子，分这个序列中最多的糖果，每个降序序列的第一个孩子，分这个序列的最多的糖果
4. 所以有一个关键点,如果两个相邻的序列长度相同，并且先升序后降序，那么升序序列的最后一个孩子的糖果，会和降序序列的第一个孩子的糖果数量一样，例如1,2,3,3,2,1

此时，升序序列1,2,3最后一个孩子，可以多分一块糖，变成1,2,4. 从而整体构成满足条件的序列1,2,4,3,2,1.

5. 特殊情况（利用程序要求的漏洞，从而分配最少得糖果）：如果两个相邻的孩子分数一样，后面那个孩子直接从1颗糖果开始，从头开始构建序列。因为，它只说相邻的孩子分数高的孩子糖要更多，如果分数相同，不需要遵循这个规则，直接给后面的孩子分配1颗

关键点在于，如果相邻孩子分数一样，无论升序还是降序序列，直接从头开始构建，这样就将糖果数量控制在最低了。

第一个元素算作升序还是降序。算作升序，因为先升序后降序完美适配这道题，如果你感到困惑，看下面的例子。

[1,2,3,1,0]为例,我们要不断记录相邻两个序列的长度，并且只关注升序在前，降序在后的情况。

1. 同学1号，先分配1块糖果。其本身默认构成升序序列（inc = 1），pre = 1（pre是前一个同学持有的糖果，现在1号同学是下一个同学的前一个同学）
2. 同学2号，发现>=同学1号，构成升序序列，给其分配2块糖果（分数高的多分配)，此时inc = 2，pre = 2；
3. 同学3号，>=同学2号，构成升序序列，分配3颗糖果，此时inc = 3.pre = 3；
4. 同学4号，<同学3号，构成降序序列(dec = 1).判断dec == inc = false，则遵循，每个降序序列的新同学都分配1块糖果，故4号同学1块糖，pre = 1

为什么要加dec == inc = false这个条件: 如果两个相邻的序列长度相同，并且先升序后降序，那么升序序列的最后一个孩子a的糖果，会和降序序列的第一个孩子b的糖果数量一样，例如1,2,3,3,2,1。但是a>b,此时a孩子必须+1.。假设同学a分配2颗糖（同学a是上一个升序序列最后一个同学，inc = 2，表示这个升序序列中，a前面就一个同学，分配1颗糖），然后后面同学都比它分数低，构成降序序列

1. 同学b分配1颗糖，构成序列为2,1，是满足条件的。因为b的分数比a小。同时b构成降序序列，目前dec = 1.
2. 同学c分数比b小，因为降序序列，新同学分1颗，此时序列为a = 2，b = 1，c = 1. 但是b比c分数高，因此b需要多分1块糖，此时序列为a = 2，b = 2，c = 1。降序序列新增一个同学，dec = 2
3. 此时dec = inc = 2. 对应的情况是，降序序列头一个同学b，和上一个升序序列最后一个同学a的糖果相同。但是a>b.此时必须多给a分一块糖（因为a比b分数高，不能和b分一样的糖），因此a+1 = 3，从而构成序列a = 3，b = 2，c = 1，这样就满足条件了

5. 同学5号，<同学4号，构成降序（dec = 2），新同学分配1块糖果，降序序列的其它同学就都得多分配一块，也就是4号同学多分一块，此时4号同学2块糖，5号同学1块糖。并且dex == inc =false，不用考虑对前面升序序列做操作

代码

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int ret = 1;//最终答案，初始为1，代表第一个孩子，无论大小先给他一块糖
        //pre是上一个孩子获取的糖。
        //算法的关键在于处理两个相邻的升序+降序序列，dec记录当前降序序列长度，
        //inc记录上一个升序序列长度，初始为1，默认第一个孩子构成升序序列
        int inc = 1, dec = 0, pre = 1;
        for (int i = 1; i < n; i++) {//从第二个孩子开始
            if (ratings[i] >= ratings[i - 1]) {//如果当前孩子分数>前一个，则当前构成升序序列
                dec = 0;//降序序列的长度归0
                //如果当前孩子分数 == 上一个，则重新开始构建序列，直接从1开始分配糖果
                //如果当前>上一个，则继续构成升序序列，pre+1给当前孩子多分配一块糖
                pre = ratings[i] == ratings[i - 1] ? 1 : pre + 1;
                ret += pre;//将给当前孩子分配的糖果计入ret
                inc = pre;//升序序列个数正好和分配的糖的数量是一致的，因为我们是1块一块叠加分配，正好构成升序序列
            } else {//当前孩子分数<前一个，则开始构成降序序列
                dec++;//降序序列长度+1
                if (dec == inc) dec++;//如果当前降序序列长度 == 上一次的升序序列长度，则上一次升序序列最后一个孩子a分配的糖果 == 当前降序序列第一个孩子b的。但是a的分数>b .所以a孩子必须多分配一个糖果
                ret += dec;//降序序列给最后一个新同学一块糖果，前面的都得+1, +1的个数正好是dec的个数
                pre = 1;//降序序列的最后一个同学，都分配1颗糖果
            }
        }
        return ret;
    }
}