贪心算法

基本概念

• 贪心算法：求解问题时，每一步都采取基于当前环境下的最优选择
• 贪心算法&动态规划：动态规划会记录每一步的环境和结果，方便回退；贪心算法不可回退

122. 买卖股票的最佳时机 II（easy）

方法一：峰谷法

如果我们分析图表，那么我们的兴趣点是连续的峰和谷。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int i = 0;
        int valley = prices[0];
        int peak = prices[0];
        int maxprofit = 0;
        while (i < prices.size() - 1) {
            while (i < prices.size() - 1 && prices[i] >= prices[i + 1])
                i++;
            valley = prices[i];
            while (i < prices.size() - 1 && prices[i] <= prices[i + 1])
                i++;
            peak = prices[i];
            maxprofit += peak - valley;
        }
        return maxprofit;
    }
};

方法二：简单的一次遍历

直接继续增加加数组的连续数字之间的差值，如果第二个数字大于第一个数字，我们获得的总和将是最大利润。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int maxprofit = 0;
        for(int i=1;i<prices.size();i++)
        {
            maxprofit += max(prices[i]-prices[i-1],0); 
        }
        return maxprofit;
    }
};

406. 根据身高重建队列(Medium)

利用一个原理：个子矮的人相对于个子高的人是 “看不见” 的
该策略可以递归进行：

• 将最高的人按照 k 值升序排序，然后将它们放置到输出队列中与 k 值相等的索引位置上。
• 按降序取下一个高度，同样按 k 值对该身高的人升序排序，然后逐个插入到输出队列中与 k 值相等的索引位置上。
• 直到完成为止。 ```cpp // list随机插值，最后再转存vector作为答案，速度快，内存占用高 class Solution { public: vector> reconstructQueue(vector>& people) {

    if(people.size()<=1)
    return people;

    sort(people.begin(),people.end(),[](vector<int> &a,vector<int> &b)
    {return a[0]>b[0]||(a[0]==b[0]&&a[1]<b[1]);});
    int lash_h=0;
    list<vector<int>> ans;
    for(auto p:people)
    {
        if(p[0]<=lash_h)
        {
            list<vector<int>>::iterator it = ans.begin();
            for(int i=0;i<p[1];i++)
            {
                it++;
            }
            ans.insert(it,p);
        }
        else
        {
            ans.push_back(p);
        }
        lash_h = p[0];
    }
    vector<vector<int>> ans_vector;
    for(auto a:ans)
    {
        ans_vector.push_back(a);
    }
    return ans_vector;
}

}; ```