leetcode135. Candy

shmily 發(fā)布于2019-08-15 14:26 / 3018人閱讀

摘要：題目要求假設(shè)有個孩子站成一排，每個孩子擁有一個評估值。我們可以觀察到，每次最遠(yuǎn)只需要額外分發(fā)到距離當(dāng)前最近的評分最高的那個孩子。因為他的糖果數(shù)量的增加并不會影響到之前孩子。當(dāng)有多個最近評分最高的孩子時，則選擇最后一個。

題目要求

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?

假設(shè)有N個孩子站成一排，每個孩子擁有一個評估值。現(xiàn)在要根據(jù)以下的需求給孩子們分發(fā)糖果：

每個孩子至少有一顆糖

有更高評估值的孩子應(yīng)當(dāng)比兩側(cè)孩子得到的糖更多

問最少要發(fā)出多少顆糖？

思路和代碼

這里我們可以舉一個例子來先試著分配一下：
假設(shè)有10個孩子，每個孩子對應(yīng)的評估分別是[3,4,5,7,2,3,3,2,1,10]
按照盡量少分配的原則，前四個孩子我們會分別給1，2，3，4顆糖，從第五個孩子開始，我們只需要給1顆糖就可以滿足需求。

前五個孩子的分配情況如下：
[1,2,3,4,1, , , , , ]

第六個孩子和第七個孩子評估值相同，我們還是可以將第七個孩子賦值1，因為這樣還是可以滿足要求。結(jié)果如下：
[1,2,3,4,1,2,1, , , ]

到第八個孩子的時候，我們發(fā)現(xiàn)這個孩子評估值比第七個孩子低，但是基于每個孩子最少一顆糖的原理，我們必須給第八個孩子一顆糖并且開始回調(diào)前面分發(fā)的糖的數(shù)量。
[1,2,3,4,1,2,2,1, , ]

第九個孩子的情況一樣，我們同樣給他一顆糖并調(diào)整：
[1,2,3,4,1,2,3,2,1, ]

最后孩子評分比前一個評分高，我們只需直接在前一個孩子的數(shù)量上加1即可：
[1,2,3,4,1,2,3,2,1,2]

由此我們可以總結(jié)出以下幾個結(jié)論：

當(dāng)后一個孩子比前一個孩子評分高時，直接在前一個孩子糖果數(shù)量基礎(chǔ)上加1

當(dāng)后一個孩子比前一個孩子評分低時

前一個孩子糖果數(shù)量大于1，則該孩子糖果數(shù)量為1

前一個孩子糖果數(shù)量為1，則該孩子糖果數(shù)量為1，并且將前面相應(yīng)孩子的糖果數(shù)量加1

當(dāng)后一個孩子和前一個孩子評分一樣多，則該孩子糖果數(shù)量為1

這是我們只需要知道，當(dāng)后一個孩子比前一個孩子評分低，且前一個孩子糖果數(shù)量為1時，最少由多少個孩子需要額外分發(fā)一個糖果。我們可以觀察到，每次最遠(yuǎn)只需要額外分發(fā)到距離當(dāng)前最近的評分最高的那個孩子。因為他的糖果數(shù)量的增加并不會影響到之前孩子。
至于該評分最高的孩子是否需要增加糖果，則要看后面的孩子增加后的糖果數(shù)量是不是比他高。

當(dāng)有多個最近評分最高的孩子時，則選擇最后一個。

代碼如下：

    public int candy(int[] ratings) {
        int count = 1;
        int summitIndex = 0;
        int summitCandy = 1;
        int prevCandy = 1;
        for(int i = 1 ; i ratings[i-1]){
                prevCandy++;
                count += prevCandy;
                summitIndex = i;
                summitCandy = prevCandy;
            }else if(ratings[i] < ratings[i-1]){
                if(prevCandy == 1){
                    count += (i - summitIndex) + (i-summitIndex >= summitCandy ? 1 : 0);
                }else{
                    prevCandy = 1;
                    count += prevCandy;
                }
            }else{
                prevCandy = 1;
                count += prevCandy;
                summitIndex = i;
                summitCandy = prevCandy;
            }
        }
        return count;
    }

想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號！將會不定期的發(fā)放福利哦~