leetcode-135 分發糖果

題目描述：

老師想給孩子們分發糖果，有 N 個孩子站成了一條直線，老師會根據每個孩子的表現，預先給他們評分。

你需要按照以下要求，幫助老師給這些孩子分發糖果：

每個孩子至少配置設定到 1 個糖果。

相鄰的孩子中，評分高的孩子必須獲得更多的糖果。

那麼這樣下來，老師至少需要準備多少顆糖果呢？

示例 1:

輸入: [1,0,2]

輸出: 5

解釋: 你可以分别給這三個孩子分發 2、1、2 顆糖果。

示例 2:

輸入: [1,2,2]

輸出: 4

解釋: 你可以分别給這三個孩子分發 1、2、1 顆糖果。

第三個孩子隻得到 1 顆糖果，這已滿足上述兩個條件

方法一：（暴力搜尋）

兩個條件：

1. 每個孩子至少配置設定到 1 個糖果
2. 相鄰的孩子中，評分高的孩子必須獲得更多的糖果

即先給所有孩子配置設定一個糖果

滿足第二個條件的要求是：

a. ratings[i] > ratings[i-1] 且 candy[i] <= candy[i-1]，此時candy[i]的糖果數量需要在candy[i-1]的基礎上增加1(保證最終結果最小)

b. ratings[i] > ratings[i+1] 且 candy[i] <= candy[i+1], 此時candy[i]的糖果數量需要在candy[i+1]的基礎上增加1

實作如下:

int candy(vector<int>& ratings) {
    vector<int> candy(ratings.size(),1);

    bool flag = true;
    while (flag) {
        flag = false;
        for (int i = 0;i < ratings.size(); ++i) {
            if (i != ratings.size() - 1 && ratings[i] > ratings[i+1] &&
                                            candy[i] <= candy[i+1]) 
            {
                candy[i] = candy[i+1] + 1;
                flag = true;
            }

            if (i > 0 && ratings[i] > ratings[i-1] && candy[i] <= candy[i-1]) {
                candy[i] = candy[i-1] + 1;
                flag = true;
            }
        }
    }
    
    int sum = 0;
    for (int i = 0;i < candy.size(); ++i) {
        sum += candy[i];
    }
    return sum;
}      

以上方法最壞的時間複雜度：

O(n^2),對于每個元素，我們最多要周遊n次

方法二：前後周遊

取出條件2: 相鄰的孩子中，評分高的孩子必須獲得更多的糖果

即必須同時滿足：

1. a. ratings[i] > ratings[i-1] && candy[i] > candy[i-1]
2. b. ratings[i] > ratings[i+1] && candy[i] > candy[i+1]

針對第一種情況，我們可以從左向右周遊一次即可滿足

針對第二種情況，我們可以從右向左周遊一次即可滿足

int candy(vector<int>& ratings) {
    vector<int> candy(ratings.size(),1);

    //從左向右
    for (int i = 1; i < ratings.size(); ++i) {
        if (ratings[i] > ratings[i-1] && candy[i] <= candy[i-1]){
            candy[i] = candy[i-1] + 1;
        }
    }
    
    //從右向左
    for (int i = ratings.size() - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i+1] && candy[i] <= candy[i+1]) {
            candy[i] = candy[i+1] + 1;
        }
    }
    
    int sum = 0;
    for (int i:candy) {
        sum += i;
    }
    return sum;
}