DAY17-贪心

其实贪心只是一种思路，时常体现在各种算法里面，像之前讲的最小生成树(prim)，最短路径(Dijkstra)就是展现了贪心的思路。

最小生成树 - prim
((用priority_queue(堆)实现贪心思想(利用pq来搜索路径)
((取出pq最前面的元素，放入相邻的节点))
最短路径 - Disjkstra
((基於贪心思想，从起点找一个离起点最近的节点->这一个边无法再松弛->用这一个边去对其他边松弛))

这种题目也没有固定的做法，只是遵循这种思路再去设计贪心的策略，就整理几题~~

例题实战

122. 买卖股票的最佳时机 II
这题乍看下是DP，但其实贪心思路是可以求出答案的~~
原因是最佳解就只是每一段上升价差的和((掌握到最好的价差时间，也只能获得每一段价差和))，所以是一个贪心思路，直接算整个数组上升和

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

1833. 雪糕的最大数量
没别的..就先从便宜的开始买..

class Solution {
public:
    int maxIceCream(vector<int>& costs, int coins) {
        sort(costs.begin(), costs.end());
        int res = 0;
        for(int i = 0; i<costs.size(); ++i){
            if(coins>=costs[i]){
                coins-=costs[i];
                res++;
            }
        }
        return res;
    }
};

11. 盛最多水的容器
贪心思路：从两侧开始移动，比较左右边界，如果其中一侧比较矮，先移动那一侧(才有可能使容量变大)

class Solution {
public:
    int maxArea(vector<int>& height) {
        int res = 0;
        int l = height.size()-1;
        int r = 0;
        while(r<l){
            res = max(res, (l-r)*min(height[l], height[r]));
            if(height[r]<height[l]){
                r++;
            }
            else{
                l--;
            }
        }
        return res;
    }
};