C++第二阶段——数据结构和算法，之前学过一点点数据结构，当时是基于Python来学习的，现在基于C++查漏补缺，尤其是树的部分。这一部分计划一个月，主要利用代码随想录来学习，刷题使用力扣网站，不定时更新，欢迎关注！

一、376. 摆动序列

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if(nums.size()==1) return 1;
        int before=0;// 记录前坡度
        int after=0; // 记录后坡度
        int result;
        for(int i=0;i<nums.size()-1;i++){
            after = nums[i+1]-nums[i];
            if((before>=0&&after<0)||(before<=0&&after>0)){
                result++;
                // 此时更新before
                before = after;
            }
        }
        return result;
    } 
};

二、738.单调递增的数字

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string num = to_string(n);
        int flag =num.size();
        for(int i=num.size()-1;i>0;i--){
            if(num[i] < num[i-1]){
                flag = i;
                num[i-1]--;
            }
        }
        for(int i= flag;i<num.size();i++){
            num[i] = '9';
        }
        return stoi(num);
    }
};

三、122. 买卖股票的最佳时机 II

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // 收集每天的正利润
        int result =0;
        for(int i=0;i<prices.size()-1;i++){
            if(prices[i+1]-prices[i]>0){
                result+= (prices[i+1]-prices[i]);
            }
        }
        return result;
    }
};

四、135. 分发糖果

class Solution {
public:
    int candy(vector<int>& ratings) {
        // 定义一个列表用来存放每个孩子应得的糖果数，最后遍历获得结果
        vector<int> v(ratings.size(),1);
        int result =0;
        // 先处理右边，如果右孩子比左孩子分数高，那么右孩子+1；
        for(int i=1;i<ratings.size();i++){
            if(ratings[i]>ratings[i-1]){
                v[i] =v[i-1]+1;
            }

        }
        // 再处理左边，如果左孩子比右孩子分数高，那么左孩子+右孩子的糖果，从后向前遍历
        for(int i=ratings.size()-2;i>=0;i--){
            if(ratings[i]>ratings[i+1]){
                v[i] = max(v[i],v[i+1]+1);
            }
        }
        for(int num:v){
            result+= num;
        }
        return result;
    }
};

五、406. 根据身高重建队列

class Solution {
public:
    // 根据身高先对数组进行重新排列
    static bool cmp(const vector<int> &a,const vector<int> &b){
        if(a[0]== b[0]) return a[1]<b[1];
        return a[0]>b[0];
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(),people.end(),cmp);
        // 遍历然后重新排序
        vector<vector<int>> que;
        for(int i=0;i<people.size();i++){
            // 根据k进行插入
            int k = people[i][1];
            que.insert(k+que.begin(),people[i]);
        }
        return que;
    }
};