本文共 6793 字，大约阅读时间需要 22 分钟。

https://oj.leetcode.com/problems/candy/

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

• Each child must have at least one candy.
• Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

public int candy(int[] ratings)

这一题的关键点就是二维坐标轴里的极小点的判定。其中x轴表示的是数组的index, y轴表示的是数组index对应的rating值。所有极小点都是1，然后其他点的值就是它与它左侧极小点的距离（当处于上升曲线）或者它与它右侧极小点的距离（当处于下降曲线）又或者是1（当处于一个平行于x轴的线，也就是处于连续相等的rating值之间）。

基于上述原理，要设计这一题的O(N)算法我们需要以下几个要素:快慢指针，一个状态机，可能还需要一个记录数组。主要目的，都是在于跟踪当前点是属于上升曲线还是下降，或者平线，而且还需要知道当前点是否为极点。假设起点为一个极小点，所以起始值是1，如果上升，则不停叠加，如果下降，则递减。快慢指针的用处主要在于让慢指针停留在一个极大点，然后当块指针遇到终点或者极小点的时候，慢指针一步步回归块指针的位置并基于与块指针的距离计算当前位置的糖果个数。其余的时候其实慢指针并没有用处。下面给出一个O（N）时间和O（N）空间的代码，O（N）空间主要是记录每一次计算出来的当前位置的糖果数目。

private int calculate(int[] candies, int slow, int end, int curstatus){        if(curstatus != -1)            return slow;        int diff = candies[end] - 1;        candies[slow] = diff < 0 ? candies[slow] - diff : candies[slow];        slow++;        while(slow <= end){            candies[slow] -= diff;            slow++;        }        return slow;    }    public int candy(int[] ratings) {        if(ratings == null || ratings.length == 0)            return 0;        int curstatus = 0;//0 means equal, 1 means increasing, -1 means decreasing;        int[] candies = new int[ratings.length];        int res = 0;;        candies[0] = 1;        int slow = 0;        for(int i = 1; i < ratings.length; i++){            if(ratings[i] == ratings[i - 1]){                slow = calculate(candies, slow, i - 1, curstatus);                candies[i] = 1;                curstatus = 0;                slow = i;            }else if(ratings[i] > ratings[i - 1]){                slow = calculate(candies, slow, i - 1, curstatus);                candies[i] = candies[i - 1] + 1;                slow = i;                curstatus = 1;            }else{                curstatus = -1;                candies[i] = candies[i - 1] - 1;            }        }        calculate(candies, slow, candies.length - 1, curstatus);        for(int i = 0; i < candies.length; i++)            res += candies[i];        return res;    }

public int candy(int[] ratings) {        int slow_pointer = 0, fast_pointer = 1, res = 1, cur_candy = 1, curstatus = 0;        for(; fast_pointer < ratings.length; fast_pointer++){            if(ratings[fast_pointer] == ratings[fast_pointer - 1]){                if(curstatus == -1){                    int diff = cur_candy - 1;                    res -= diff < 0 ? (fast_pointer - slow_pointer) * diff : (fast_pointer - slow_pointer - 1) * diff;                }                cur_candy = 1;                res += cur_candy;                slow_pointer = fast_pointer;                curstatus = 0;            }else if(ratings[fast_pointer] > ratings[fast_pointer - 1]){                if(curstatus == -1){                    int diff = cur_candy - 1;                    res -= diff < 0 ? (fast_pointer - slow_pointer) * diff : (fast_pointer - slow_pointer - 1) * diff;                    cur_candy = 1;                }                cur_candy++;                res += cur_candy;                slow_pointer = fast_pointer;                curstatus = 1;            }else{                cur_candy--;                res += cur_candy;                curstatus = -1;            }        }        if(curstatus == -1){            int diff = cur_candy - 1;            res -= diff < 0 ? (fast_pointer - slow_pointer) * diff : (fast_pointer - slow_pointer - 1) * diff;        }        return res;    }

稍微简洁了一下代码和状态更新。

public int candy(int[] ratings) {        int curCandy = 1, result = 1, slowPointer = 0;        for(int i = 1; i < ratings.length; i++){            if(ratings[i] < ratings[i - 1] && (i == ratings.length - 1 || ratings[i] <= ratings[i + 1])){                curCandy--;                result += curCandy;                int diff = curCandy - 1;                result -= (i - slowPointer) * diff + (diff < 0 ? diff : 0);                slowPointer = i;                curCandy = 1;            }else if(ratings[i] > ratings[i - 1]){                slowPointer = i;                curCandy++;                result += curCandy;            }else if(ratings[i] == ratings[i - 1]){                slowPointer = i;                curCandy = 1;                result += curCandy;            }else {                curCandy--;                result += curCandy;            }        }        return result;    }

2018-01-18 Updated

重新写了一遍答案并附注了代码上的解释：

public int candy(int[] ratings) {        int slowPointer = 0, curCandy = 1, result = 1;        for (int i = 1; i < ratings.length; i++) {            // Case 1. 极小点            // 这是一个比较总和的case, 这个点必然为1。而slowPointer和本点之间的点都会呈距离为一的递减状态。            // 当然slowPointer自身的值是与左右两边极点的距离 + 1的较大值。            if (ratings[i] < ratings[i - 1] && (i == ratings.length - 1 || ratings[i + 1] >= ratings[i])) {                // 先照常按照递减去计算当前的curCandy                curCandy--;                result += curCandy;                // 我们此时重置curCandy为1，并且将slowPointer和i之间的点根据curCandy为1的情况，自右向左递增1。                // 下面讲解一下为何下面的做法可以达到上面的目的                // 譬如slowPointer所对应的curCandy是8，当前i点所对应的curCandy是3                // 所以slowPointer到i之间就是8,7,6,5,4,3。所以我们要计算1和3的差，这就是7,6,5,4这四个点可以往下减的量                // 此时slowPointer到i之间就变成了8,5,4,3,2,1。 之前说了，slowPointer所对应的点所需要的candy是根据它与左边极小点和右边                // 极小点的距离的较大者，此时slowPointer是8。表示它与左边相邻的极小点的距离是7，然后它和右边极小点的距离是5。所以它不会产生变化                // 但如果slowPointer到i之间是4,3,2,1,0,-1 此时slowPointer到i的距离更大， 所以slowPointer对应的点也需要改变。                // 序列就会变成 6,5,4,3,2,1                int diff = 1 - curCandy;                // diff > 0 是 判断slowPointer所处的极大点距离当前点比左边的极小点更远，所以我们要算上，否则就不用了。                result += (i - slowPointer) * diff + (diff > 0 ? diff : 0);                slowPointer = i;                curCandy = 1;            } else if (ratings[i] < ratings[i - 1]) {                // case 2 : 递减。 此时slowPointer留在先前的极大点，不需要操作                curCandy--;                result += curCandy;            } else if (ratings[i] > ratings[i - 1]) {                // case 3 : 递增。 slowPointer跟上，slowPointer的任务总是尝试停留在一个极大点。                slowPointer = i;                curCandy++;                result += curCandy;            } else {                // case 4 : 相等，这是一个特例，因为规矩没有规定如果邻居和我们同rating是什么情况。所以可以设定当前为最小的1.                // 然后如果之后呈现递减（也就是当前是一个极大点的线段），那么case 1会将当前点push到它所应该在的位置                // 如果之后呈现递增，当前点等同于一个极小点的线段（虽然可能不是真的极小点）。起点为1也是对的                curCandy = 1;                result += curCandy;                slowPointer = i;            }        }                return result;    }

转载地址：http://ggaxb.baihongyu.com/