[数据结构与算法]LeetCode 135 分糖果

• 分析
  把数据放到最小堆里面，然后依次取出进行处理，从小到大处理，一次循环就可以找出所需的最少糖果数。这个思想可以引申到小孩围成圈的情况。
• 代码

struct node{
    int index;
    int rating;
};

struct fun{
		//重写仿函数
    bool operator()(const node& node1, const node& node2){
        return node1.rating > node2.rating;
    }
};

class Solution {
public:
    int candy(vector<int>& ratings) {
        priority_queue<node, vector<node>, fun> que;
        int size = ratings.size();   
        if(size == 1) return 1;       

        vector<int> vec(size, 1);
        for(int i = 0; i < size; i++){
            que.push(node{i, ratings[i]});
        }

        int ans = 0;
        while(!que.empty()){
            node temp(que.top());
            que.pop();

            int index = temp.index;
            if(index == 0){
                if(ratings[index] > ratings[index + 1]){
                    vec[index] = vec[index + 1] + 1;
                }
            }else if(index == size - 1){
                if(ratings[index] > ratings[index - 1]){
                    vec[index] = vec[index - 1] + 1; 
                }
            }else{
                if(ratings[index] > max(ratings[index + 1], ratings[index - 1])){
                    vec[index] = max(vec[index + 1], vec[index - 1]) + 1;
                }else if((ratings[index] <= min(ratings[index + 1], ratings[index - 1]) || (ratings[index]==ratings[index +1]&&ratings[index]==ratings[index -1]))){
                    continue;
                }else{
                    int minrindex =index + 1;
                    if(ratings[index - 1] < ratings[index + 1]){
                        minrindex = index - 1;
                    }

                    vec[index] = vec[minrindex] + 1;
                }                                            
            }
        }
        for(int n:vec){
            ans += n;
        } 
        return ans;
    }
};