Leetcode 135. 分发糖果 贪心模拟题目

 

思路1：直接模拟糖果的分配方案，不断的从0到n-1分配糖果，直到分配的满足要去，时间复杂度O(n^2), 模拟

只有Java的代码能过，C++的代码过不了

public class Solution {
    public int candy(int[] ratings) {
        int[] candies = new int[ratings.length];
        Arrays.fill(candies, 1);
        boolean flag = true;
        int sum = 0;
        while (flag) {
            flag = false;
            for (int i = 0; i < ratings.length; i++) {
                if (i != ratings.length - 1 && ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) {
                    candies[i] = candies[i + 1] + 1;
                    flag = true;
                }
                if (i > 0 && ratings[i] > ratings[i - 1] && candies[i] <= candies[i - 1]) {
                    candies[i] = candies[i - 1] + 1;
                    flag = true;
                }
            }
        }
        for (int candy : candies) {
            sum += candy;
        }
        return sum;
    }
}

优化方案:

先排序一次，然后从低分到高分，不断发糖果这样的时间复杂度可以优化到O(nlogn)

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        vector<int> nums(n, 1);        
        vector<pair<int,int>> helper;          // 存下分数和编号
        for(int i=0;i<n;i++) helper.push_back(make_pair(ratings[i],i));
        sort(helper.begin(),helper.end());
        for(int i=0;i<n;i++){
            int rating = helper[i].first, index = helper[i].second;
            if(index>0&&rating>ratings[index-1]&&nums[index]<=nums[index-1]) nums[index] = nums[index-1]+1;
            if(index<n-1&&rating>ratings[index+1]&&nums[index]<=nums[index+1]) nums[index] = nums[index+1]+1;
        }
        int count = 0;
        for(int i=0;i<n;i++) count+=nums[i];
        return count;

    }
};

进一步优化，左右规则分离

单独满足左规则，记录下糖果分配方案，单独满足右规则，记录下糖果方案，这样一次分配就能解决。时间复杂度O(n)

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        vector<int> left(n,1), right(n,1);
        int res = 0;
        for(int i=1;i<=n-1;i++){
            if(ratings[i]>ratings[i-1]&&right[i]<=right[i-1]) right[i] = right[i-1]+1; 
        }
        res+=right[n-1];
        for(int i=n-2;i>=0;i--){
            if(ratings[i]>ratings[i+1]&&left[i]<=left[i+1]) left[i] = left[i+1]+1;
            res+=max(right[i],left[i]);
        }
        return res;
    }
};