「算法刷题」贪心算法的相关题目(困难难度)

贪心算法是一种常见的算法思想，其特点就是通过每次都选择局部最优来达到实现全局最优的目的。

例如让你从一堆钞票中拿走10张，你为了达到拿到最大金额的目的，必定会每次都拿走最大面额的钞票，这就是贪心算法的思想。本博客是记录作者做贪心算法的较困难的题的笔记。

一、贪心算法的权衡问题

LeetCode题目	相关题目类型	题目类型分析	题目思路	相关链接
135	分发糖果（困难难度）			https://leetcode-cn.com/problems/candy/
406	根据身高重建队列（中等难度）	根据两个维度给数组排序	按照身高从高到低排序，然后根据k维度进行插入	https://leetcode-cn.com/problems/queue-reconstruction-by-height/

406 根据身高重建队列

本题有两个维度，h和k，看到这种题目一定要想如何确定一个维度，然后在按照另一个维度重新排列。

按照身高h来排序呢，身高一定是从大到小排（身高相同的话则k小的站前面），让高个子在前面。

那么只需要按照k为下标重新插入队列就可以了，为什么呢？

以图中{5,2} 为例：

代码如下：

	static bool cmp(vector<int> &a,vector<int> &b){
        if(a[0]==b[0])// 如果身高相同则按照k从小到大排列
        {
            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;
        // 按照k调整队列
        for (int i = 0; i < people.size(); i++) {
            int position = people[i][1];
            que.insert(que.begin() + position, people[i]);
        }
        return que;
    }

按照身高排序之后，优先按身高高的people的k来插入，后序插入节点也不会影响前面已经插入的节点，最终按照k的规则完成了队列。

但使用vector是非常费时的，C++中vector（可以理解是一个动态数组，底层是普通数组实现的）如果插入元素大于预先普通数组大小，vector底部会有一个扩容的操作，即申请两倍于原先普通数组的大小，然后把数据拷贝到另一个更大的数组上。

所以使用vector（动态数组）来insert，是费时的

二、贪心算法的树题目

LeetCode题目	相关题目类型	题目类型分析	题目思路	相关链接
968	监控二叉树（困难难度）			https://leetcode-cn.com/problems/binary-tree-cameras/

968 监控二叉树

代码如下：