【代码随想录】第10章 贪心算法

第10章 贪心算法

贪心没有固定的模板套路

如果找出局部最优并可以推出全局最优,就是贪心;如果局部最优都没有找出来,就不是贪心,可能是单纯的模拟。

贪心算法一般分为如下四步:

  • 将问题分解为若干个子问题
  • 找出适合的贪心策略
  • 求解每一个子问题的最优解
  • 将局部最优解堆叠成全局最优解

刷题或者面试的时候,手动模拟一下感觉可以局部最优推出整体最优,而且想不到反例,那么就试一试贪心

【代码随想录】第10章 贪心算法

455. 分发饼干【简单】

【代码随想录】第10章 贪心算法

思路:小饼干给小胃口

同样可以反过来,大饼干给大胃口

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int j = 0;  //定位g,即胃口   这里必须初始化,要不然报错
        for(int i = 0; i < s.size(); i++) {  //遍历饼干
            if(j < g.size() && s[i] >= g[j]) {  //前面的判断条件防止超出索引
                j++;
            }
        }
        return j;   //索引就是人数
    }
};

376. 摆动序列【中等】

【代码随想录】第10章 贪心算法

【代码随想录】第10章 贪心算法

题目意思:就是找极大极小值的个数

  • 思路一:贪心

时间复杂度:O(n)

空间复杂度:O(1)

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if (nums.size() < 2)   return nums.size();

        int preDiff = nums[1] - nums[0];
        int res = preDiff != 0 ? 2 : 1;
        for(int i = 2; i < nums.size(); ++i){
            int curDiff = nums[i] - nums[i-1];
            //出现峰值
            if((preDiff<=0 && curDiff>0) || (preDiff>=0 && curDiff<0)){
                res++;
                preDiff = curDiff;
            }
        }
    	return res;
    }
};

思路二:动态规划

53. 最大子数组和【简单】

相同题目:剑指 Offer 42. 连续子数组的最大和

【代码随想录】第10章 贪心算法

思路一:双for循环暴力破解:计算从每一个索引开始的最大子序和

//两for循环暴力破解
//计算从索引0开始的的最大子字符串, 从1开始, 从2开始......
//时间复杂度:O(n^2),  超出时间限制的
class Solution
{
public:
    int maxSubArray(vector<int>& nums){
        //类似寻找最大最小值的题目,初始值一定要定义成理论上的最小值 或 最大值
        int sumMax = INT_MIN;
        for (int i = 0; i < nums.size(); i++){
            int sum = 0;
            for (int j = i; j < nums.size(); j++){
                sum += nums[j];
                sumMax = max(sum, sumMax);
            }
        }

        return sumMax;
    }
};

思路二:动态规划

思路可查看此人的PPT:https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-cshi-xian-si-chong-jie-fa-bao-li-f/

时间复杂度:O(n)

空间复杂度:O(n)

class Solution {
public:
    int maxSubArray(vector<int>& nums) {		
		//先替换元素  更新数组
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i - 1] > 0) {          //如果前一个元素>0   后一个元素改为两者之和
                nums[i] = nums[i - 1] + nums[i];
            }
        }

		//再遍历查找最大值
        int res = nums[0];
        for (int i : nums) {
            res = max(res, i);
        }

        return res;
    }
};

我们可以对两个并行for循环进行优化,只用一个for循环解决

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res = nums[0];

        for (int i = 1; i < nums.size(); i++) {
            if (nums[i - 1] > 0) {
                nums[i] = nums[i - 1] + nums[i];
            }
            if (nums[i] > res) {
                res = nums[i];
            }
        }

        return res;
    }
};

接着优化缩短代码,往官方参考答案靠近

  • [x]
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res = nums[0];

        for (int i = 1; i < nums.size(); i++) {
            nums[i] = max(nums[i], nums[i - 1] + nums[i]);  //主要是这句代码
            res = max(res, nums[i]);                        //动态记录最大子序和
        }

        return res;
    }
};

代码随想录动态规划的思路:

五部曲:

  1. 确定dp数组(dp table)以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组
【代码随想录】第10章 贪心算法
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        
        vector<int> dp(nums.size());
        dp[0] = nums[0];
        int res = dp[0];
        
        for (int i = 1; i < nums.size(); i++) {
            dp[i] = max(dp[i - 1] + nums[i], nums[i]); // 状态转移公式
            res = max(dp[i], res);                     // res 保存dp[i]的最大值      
        }
        
        return res;
    }
};
  • 思路三:贪心

时间复杂度:O(n)

空间复杂度:O(1)

思路查看:https://leetcode-cn.com/problems/maximum-subarray/solution/dai-ma-sui-xiang-lu-53-zui-da-zi-xu-he-b-8d7l/

贪心贪的是哪里呢?

如果 -2 1 在一起,计算起点的时候,一定是从1开始计算,因为负数只会拉低总和,这就是贪心贪的地方!

局部最优:当前“连续和”为负数的时候立刻放弃,从下一个元素重新计算“连续和”,因为负数加上下一个元素 “连续和”只会越来越小。

全局最优:选取最大“连续和”

局部最优的情况下,并记录最大的“连续和”,可以推出全局最优。

【代码随想录】第10章 贪心算法

class Solution{
public:
    int maxSubArray(vector<int>& nums){
        //类似寻找最大最小值的题目,初始值一定要定义成理论上的最小最大值
        int res = INT_MIN;
        int sum = 0;
        for (int i = 0; i < nums.size(); i++){
            sum += nums[i];
            res = max(res, sum);
            
            //如果sum < 0,重新开始找子序串
            if (sum < 0){
                sum = 0;
            }
        }

        return res;
    }
};

1005. K 次取反后最大化的数组和【简单】

【代码随想录】第10章 贪心算法

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int nums_min = INT_MAX;
        int res = 0;
        for(int i = 0; i < nums.size(); i++){
            if(k > 0 && nums[i] < 0){
                nums[i] = -nums[i];
                k--;
            }
            res += nums[i];
            nums_min = min(nums_min, nums[i]);
        }
        
        if(k % 2 == 0) return res;
        else return res - 2*nums_min;
    }
};
  • 主要会写绝对值排序就行
class Solution {
static bool cmp(int a, int b) {   //绝对值从大到小排序
    return abs(a) > abs(b);
}
    
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end(), cmp);       // 第一步:以绝对值大小排序,从大到小
        
        for (int i = 0; i < nums.size(); i++) {    // 第二步:-改+
            if (nums[i] < 0 && k > 0) {
                nums[i] = -nums[i];
                k--;
            }
        }
        
        if (k % 2 == 1)  nums[nums.size() - 1] *= -1; // 第三步:k还有多,看是否需要修改最小值的正负号
        
        int res = 0;
        for (int num : nums)  res += num;        // 第四步:收集
        return res;
    }
};

134. 加油站【中等】

【代码随想录】第10章 贪心算法

思路一:暴力破解

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        for (int i = 0; i < cost.size(); i++) {
            int rest = gas[i] - cost[i]; // 记录剩余油量
            if (rest < 0)  continue;
            
            int index = (i + 1) % cost.size(); //下一个加油站的索引
            while (rest >= 0 && index != i) {  // 模拟以i为起点行驶一圈
                rest += gas[index] - cost[index];
                index = (index + 1) % cost.size();
            }
            
            // 如果以i为起点跑一圈,剩余油量>=0,返回该起始位置
            if (rest >= 0 && index == i) return i;
        }
        return -1;
    }
};

思路二:贪心

  • 情况一:如果gas的总和小于cost总和,那么无论从哪里出发,一定是跑不了一圈的
  • 情况二:rest[i] = gas[i]-cost[i]为一天剩下的油,i从0开始计算累加到最后一站,如果累加没有出现负数,说明从0出发,油就没有断过,那么0就是起点。
  • 情况三:如果累加的最小值是负数,汽车就要从非0节点出发,从后向前,看哪个节点能这个负数填平,能把这个负数填平的节点就是出发节点。
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int curSum = 0;
        int minSum = INT_MAX; // 从起点出发,油箱里的油量最小值
        for (int i = 0; i < gas.size(); i++) {
            int rest = gas[i] - cost[i];
            curSum += rest;
            minSum = min(minSum, curSum);
        }
        if (curSum < 0) return -1;  // 情况1
        if (min >= 0) return 0;     // 情况2
                                    // 情况3
        for (int i = gas.size() - 1; i >= 0; i--) {
            int rest = gas[i] - cost[i];
            min += rest;
            if (min >= 0) {
                return i;
            }
        }
        return -1;
    }
};
  • 思路三:贪心方法二
【代码随想录】第10章 贪心算法
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int curSum = 0;
        int totalSum = 0;   //跑完整圈后的剩余油量
        int start = 0;
        for (int i = 0; i < gas.size(); i++) {
            curSum += gas[i] - cost[i];   
            totalSum += gas[i] - cost[i];
            if (curSum < 0) {   // 当前累加rest[i]和 curSum一旦小于0
                start = i + 1;  // 起始位置更新为i+1
                curSum = 0;     // curSum从0开始
            }
        }
        
        if (totalSum < 0)    return -1; // 说明怎么走都不可能跑一圈了
        else return start;
    }
};

860. 柠檬水找零【简单】

【代码随想录】第10章 贪心算法

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int money[2] = {0,0};  //分别记录5,10元钞票多少张
        for(auto bill : bills){
            if(bill == 5){
                money[0]++;
            }
            else if(bill == 10){
                money[0]--;
                money[1]++;
                if(money[0] < 0)  return false;
            }
            else if(bill == 20){
                if(money[1] > 0){  //有10元的钞票,找零1张5元、1张10元
                    money[1]--;
                    money[0]--;
                }
                else{
                    money[0] -= 3;  //没有10元的,则找零3张5元
                }

                if(money[0] < 0)  return false;
            }
        }
        return true;
    }
};

452. 用最少数量的箭引爆气球【中等】

【代码随想录】第10章 贪心算法

【代码随想录】第10章 贪心算法

  • 以左边界排序,从小到大
class Solution {
private:
    static bool cmp(const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    }
    
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        if (points.size() == 0) return 0;
        sort(points.begin(), points.end(), cmp);

        int res = 1; // points 不为空至少需要一支箭
        for (int i = 1; i < points.size(); i++) { //两个气球及以上跑这里
            if (points[i][0] > points[i - 1][1]) {  // 气球i和气球i-1不挨着,注意这里不是>=
                res++; // 需要一支箭
            }
            else {  // 气球i和气球i-1挨着
                points[i][1] = min(points[i - 1][1], points[i][1]); // 更新重叠气球最小右边界  关键代码
            }
        }
        
        return res;
    }
};
  • 时间复杂度:O(n\log n),因为有一个快排
  • 空间复杂度:O(1)

435. 无重叠区间【中等】

【代码随想录】第10章 贪心算法

思路:统计无重叠区间个数,再总个数减一下就是result

以右边界排序

【代码随想录】第10章 贪心算法
class Solution {
public:
    // 按照区间右边界排序
    static bool cmp (const vector<int>& a, const vector<int>& b) {
        return a[1] < b[1];
    }
    
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        //if (intervals.size() == 0) return 0;
        sort(intervals.begin(), intervals.end(), cmp);
        
        int count = 1; // 记录非交叉区间的个数
        int end = intervals[0][1]; // 记录区间分割点
        for (int i = 1; i < intervals.size(); i++) {  //计算有几个无重叠区间
            if (end <= intervals[i][0]) {
                end = intervals[i][1];
                count++;
            }
        }
        
        return intervals.size() - count;
    }
};
  • 时间复杂度:O(n\log n) ,有一个快排
  • 空间复杂度:O(1)

763. 划分字母区间【中等】

【代码随想录】第10章 贪心算法

【代码随想录】第10章 贪心算法

必须两次遍历:第一次遍历更新索引,第二次遍历收集结果

class Solution {
public:
    vector<int> partitionLabels(string s) {
        int hash[26] = {0};   //存储 字符对应的最后索引
        for(int i = 0; i < s.size(); i++){  //统计每一个字符最后出现的位置
            hash[s[i] - 'a'] = i;
        }

        int right = 0;   //每个子串的开始和结束索引
        int left = 0;
        vector<int> res;
        for(int i = 0; i < s.size(); i++){
            right = max(right, hash[s[right] - 'a']);   // 找到字符出现的最远边界  这句代码很重要
            if(i == right){
                res.push_back(right - left + 1);
                left = right + 1;
            }
        }

        return res;
    }
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(1),使用的hash数组是固定大小

56. 合并区间【中等】

【代码随想录】第10章 贪心算法

自己写的:

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>> merge(vector<vector<int>>& intervals) {
        if(intervals.size() == 1)  return intervals;   //1.处理size==1的情况
        
        sort(intervals.begin(), intervals.end(), cmp);   //2.排序
        
        vector<vector<int>> res;
        for(int i = 1; i < intervals.size(); ++i){
            if(intervals[i][0] <= intervals[i-1][1]){  //核心代码
                intervals[i][0] = intervals[i-1][0];
                intervals[i][1] = max(intervals[i-1][1], intervals[i][1]);
                intervals[i-1][1] = -1;
            }
            else{
                res.push_back(intervals[i-1]);
            }
        }
        
        //处理最后一个
        if(intervals[intervals.size()-1][0] > intervals[intervals.size()-2][1]){
            res.push_back(intervals[intervals.size()-1]);
        }

        return res;
    }
};
  • 官方答案
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.size() < 2) return intervals;
        
        // 排序的参数使用了lamda表达式
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){return a[0] < b[0];});
        
        vector<vector<int>> res;
        res.push_back(intervals[0]);
        for (int i = 1; i < intervals.size(); i++) {
            if (res.back()[1] >= intervals[i][0]) { // 合并区间
                res.back()[1] = max(res.back()[1], intervals[i][1]);  //这里实现合并
            } 
            else {
                res.push_back(intervals[i]);
            }
        }
        
        return res;
    }
};
  • 时间复杂度:O(n\log n),有一个快排
  • 空间复杂度:O(1),我没有算result数组(返回值所需容器占的空间

738. 单调递增的数字【中等】

【代码随想录】第10章 贪心算法

思路一:暴力破解

一个一个减1判断是否满足条件

class Solution {
	//暴力破解  
	//时间复杂度:O(nm)  m为n的数字长度
	//空间复杂度:O(1)
public:
	bool checkNum(int num) {
		int low_pos = 10;  //记录最低位

		while (num) {
			int temp_pos = num % 10;  //拿出最低位
			if (low_pos >= temp_pos) low_pos = temp_pos;  //最低位大于次低位  更新最低位
			else return false;        //如果低位比高位小 false

			num = num / 10;
		}
		return true;
	}

	int monotoneIncreasingDigits(int N) {
		for (int i = N; i > 0; i--) {    //一个一个判断
			if (checkNum(i)) return i;
		}
		return 0;
	}
};
  • 思路二:贪心
class Solution {
public:
	int monotoneIncreasingDigits(int N) {
		string strNum = to_string(N);   //数字转字符串  string头文件的函数

        //1.找到标记位置,并使标记位的前一位-1
		int flag = strNum.size();
		for (int i = strNum.size() - 1; i > 0; i--) {    //必须从后面遍历到前面  反过来实现不了
			if (strNum[i - 1] > strNum[i]) {  //前一位>后一位
				flag = i;                     //后一位改9
				strNum[i - 1]--;              //前一位减1   332   ->  322   ->  222
			}
		}

        //2.标记位起改9
		for (int i = flag; i < strNum.size(); i++) {  //标记位置开始改9
			strNum[i] = '9';        //222 -> 299
		}

		return stoi(strNum);  //字符串转数字
	}
};
  • 时间复杂度:O(n),n 为数字长度
  • 空间复杂度:O(n),需要一个字符串,转化为字符串操作更方便

968. 监控二叉树【困难,不会】

【代码随想录】第10章 贪心算法

有如下三种:

  • 该节点无覆盖
  • 本节点有摄像头
  • 本节点有覆盖

我们分别有三个数字来表示:

  • 0:该节点无覆盖
  • 1:本节点有摄像头
  • 2:本节点有覆盖

可以使用后序遍历也就是左右中的顺序,这样就可以在回溯的过程中从下到上进行推导了。

单层逻辑处理,主要有如下四类情况:

  • 情况1:左右节点都有覆盖
    • 左孩子有覆盖,右孩子有覆盖,那么此时中间节点应该就是无覆盖的状态了。
  • 情况2:左右节点至少有一个无覆盖的情况
    • 如果是以下情况,则中间节点(父节点)应该放摄像头
  • 情况3:左右节点至少有一个有摄像头
    • 如果是以下情况,其实就是 左右孩子节点有一个有摄像头了,那么其父节点就应该是2(覆盖的状态)
  • 情况4:头结点没有覆盖
// 版本一
class Solution {
private:
    int result;
    int traversal(TreeNode* cur) {

        // 空节点,该节点有覆盖
        if (cur == NULL) return 2;

        int left = traversal(cur->left);    // 左
        int right = traversal(cur->right);  // 右

        // 情况1
        // 左右节点都有覆盖
        if (left == 2 && right == 2) return 0;

        // 情况2
        // left == 0 && right == 0 左右节点无覆盖
        // left == 1 && right == 0 左节点有摄像头,右节点无覆盖
        // left == 0 && right == 1 左节点有无覆盖,右节点摄像头
        // left == 0 && right == 2 左节点无覆盖,右节点覆盖
        // left == 2 && right == 0 左节点覆盖,右节点无覆盖
        if (left == 0 || right == 0) {
            result++;
            return 1;
        }

        // 情况3
        // left == 1 && right == 2 左节点有摄像头,右节点有覆盖
        // left == 2 && right == 1 左节点有覆盖,右节点有摄像头
        // left == 1 && right == 1 左右节点都有摄像头
        // 其他情况前段代码均已覆盖
        if (left == 1 || right == 1) return 2;

        // 以上代码我没有使用else,主要是为了把各个分支条件展现出来,这样代码有助于读者理解
        // 这个 return -1 逻辑不会走到这里。
        return -1;
    }

public:
    int minCameraCover(TreeNode* root) {
        result = 0;
        // 情况4
        if (traversal(root) == 0) { // root 无覆盖
            result++;
        }
        return result;
    }
};

跳跃游戏

55. 跳跃游戏【中等】

【代码随想录】第10章 贪心算法

class Solution {
public:
    bool canJump(vector<int>& nums) {
        if (nums.size() < 2) return true;  // 只有0,1个元素,就是能达到
        
        int cover = 0;
        for (int i = 0; i < nums.size(); i++) { 
            if(i <= cover){                       //i在覆盖范围内
                cover = max(i + nums[i], cover);  //更新覆盖范围
                if (cover >= nums.size() - 1) return true; // 说明可以覆盖到终点了
            }
            else   return false;
        }
        
        return false;  //这句走不到
    }
};

45. 跳跃游戏 II【中等】

【代码随想录】第10章 贪心算法

题目意思:最少的次数到达最后位置,假设总能到达最后位置

从图中可以看出来,就是移动下标达到了当前覆盖的最远距离下标时,步数就要加一,来增加覆盖距离。最后的步数就是最少步数。

这里还是有个特殊情况需要考虑,当移动下标达到了当前覆盖的最远距离下标时

  • 如果当前覆盖最远距离下标不是是集合终点,步数就加一,还需要继续走。
  • 如果当前覆盖最远距离下标就是是集合终点,步数不用加一,因为不能再往后走了。
class Solution {
public:
    int jump(vector<int>& nums) {
        if (nums.size() < 2) return 0;
        
        int curDistance = 0;    // 当前覆盖最远距离下标
        int ans = 0;            // 记录走的最大步数
        int nextDistance = 0;   // 下一步覆盖最远距离下标
        
        for (int i = 0; i < nums.size(); i++) {
            nextDistance = max(nums[i] + i, nextDistance);  // 记录下一步覆盖最远距离下标
            if (i == curDistance) {                        // 遇到当前覆盖最远距离下标
                if (curDistance < nums.size() - 1) {       // 如果当前覆盖最远距离下标不是终点
                    ans++;                                 // 需要走下一步
                    curDistance = nextDistance;            // 更新当前覆盖最远距离下标(相当于加油了)
                    if (nextDistance >= nums.size() - 1) break; // 下一步的覆盖范围已经可以达到终点,结束循环
                } 
                else break;     // 当前覆盖最远距离下标是集合终点,不用做ans++操作了,直接结束
            }
        }
        return ans;
    }
};

在遍历数组时,我们不访问最后一个元素,这是因为在访问最后一个元素之前,我们的边界一定大于等于最后一个位置,否则就无法跳到最后一个位置了。如果访问最后一个元素,在边界正好为最后一个位置的情况下,我们会增加一次「不必要的跳跃次数」,因此我们不必访问最后一个元素。

  • [x]
class Solution {
public:
    int jump(vector<int>& nums) {
        int curDistance = 0;    // 当前覆盖的最远距离下标
        int ans = 0;            // 记录走的最大步数
        int nextDistance = 0;   // 下一步覆盖的最远距离下标
        for (int i = 0; i < nums.size() - 1; i++) { // 注意这里是小于nums.size() - 1,这是关键所在
            nextDistance = max(nums[i] + i, nextDistance); // 记录下一步覆盖的最远距离下标
            if (i == curDistance) {                 // 遇到当前覆盖的最远距离下标
                curDistance = nextDistance;         // 更新当前覆盖的最远距离下标
                ans++;
            }
        }
        return ans;
    }
};

两个维度权衡问题

135. 分发糖果【困难】

【代码随想录】第10章 贪心算法

  • 思路一:贪心

时间复杂度:O(n)

空间复杂度:O(n)

两次遍历,一次向后,一次向前

class Solution {
public:
    int candy(vector<int>& ratings) {
        //1. 分发糖果
        vector<int> candyVec(ratings.size(), 1);  //1.1 先每人分一个
        // 从前向后
        for (int i = 1; i < ratings.size(); i++) {       
            if (ratings[i] > ratings[i - 1]) {   //1.2 右边的比左边多一个
                candyVec[i] = candyVec[i - 1] + 1;
            }
        }
        // 从后向前
        for (int i = ratings.size() - 2; i >= 0; i--) {  //确定左边>右边
            if (ratings[i] > ratings[i + 1] ) {
                candyVec[i] = max(candyVec[i], candyVec[i + 1] + 1);  //选取max是因为要保持上面的不变
            }
        }
        
        // 2. 统计结果
        int res = 0;
        for (int i = 0; i < candyVec.size(); i++) {
            res += candyVec[i];
        }
        return res;
    }
};

方法二:常数空间遍历

时间复杂度:O(n)

空间复杂度:O(1)

https://leetcode-cn.com/problems/candy/solution/fen-fa-tang-guo-by-leetcode-solution-f01p/

class Solution {
public:
    int candy(vector<int>& ratings) {
        int res = 1;
        int inc = 1;  //最近递增序列长度
        int dec = 0;  //当前递减序列长度
        int pre = 1;  //前一个同学的苹果数量
        for (int i = 1; i < ratings.size(); i++) {
            if (ratings[i] >= ratings[i - 1]) {
                dec = 0;
                pre = (ratings[i] == ratings[i - 1]) ? 1 : pre + 1;
                res += pre;
                inc = pre;
            } 
            else {
                dec++;
                if (dec == inc) {
                    dec++;
                }
                res += dec;
                pre = 1;
            }
        }
        
        return res;
    }
};

406. 根据身高重建队列【中等】

【代码随想录】第10章 贪心算法

思路:先排序,后插入

【代码随想录】第10章 贪心算法

插入的过程:

  • 插入[7,0]:[[7,0]]

  • 插入[7,1]:[[7,0],[7,1]]

  • 插入[6,1]:[[7,0],[6,1],[7,1]]

  • 插入[5,0]:[[5,0],[7,0],[6,1],[7,1]]

  • 插入[5,2]:[[5,0],[7,0],[5,2],[6,1],[7,1]]

  • 插入[4,4]:[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

  • 时间复杂度:O(n\log n + n^2)

  • 空间复杂度:O(n)

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);   //1.排序  高->低
        
        vector<vector<int>> que;
        for (int i = 0; i < people.size(); i++) {
            int position = people[i][1];
            que.insert(que.begin() + position, people[i]);  //2.插序
        }
        
        return que;
    }
};

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

  • [x]
class Solution {
public:
    // 身高从大到小排(身高相同k小的站前面)
    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);
        
        list<vector<int>> que; // list底层是链表实现,插入效率比vector高的多
        for (int i = 0; i < people.size(); i++) {
            int position = people[i][1]; // 插入到下标为position的位置
            list<vector<int>>::iterator it = que.begin();
            while (position--) { // 寻找在插入位置
                it++;
            }
            que.insert(it, people[i]);  //链表的插入速度快
        }
        
        return vector<vector<int>>(que.begin(), que.end());  //list容器->vector容器
    }
};

该方法速度更快,但是以空间换取时间

【代码随想录】第10章 贪心算法

动态数组底层会进行全量拷贝扩容,所以消耗时间

股票系列

121. 买卖股票的最佳时机【简单】

相同题目:剑指 Offer 63. 股票的最大利润

【代码随想录】第10章 贪心算法

题目意思:只能买入一次,卖出一次,最大利润

思路一:双for暴力破解;思路和53.最大子序和很像

时间复杂度:O(n^2)

空间复杂度:O(1)

class Solution {
public:
	//双for循环暴力破解   超出时间限制
	int maxProfit(vector<int>& prices) {
		int max_fit = 0;
		for (int i = 0; i < prices.size(); i++) {   
			for (int j = i + 1; j < prices.size(); j++) {
				max_fit = max(max_fit, prices[j] - prices[i]);
			}
		}

		return max_fit;
	}
};
  • 思路二:贪心

股票,去数组左边的最小值,右边的最大值,差值即为最大利润

时间复杂度:O(n) 一次for循环遍历

空间复杂度:O(1)

思路可查看代码随想录的:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/dai-ma-sui-xiang-lu-121-mai-mai-gu-piao-odhle/

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int low = INT_MAX;
        int res = 0;
        for (int i = 0; i < prices.size(); i++) {   //从左到右遍历
            low = min(low, prices[i]);              // 动态更新最小价格
            res = max(res, prices[i] - low);     // 动态更新最大利润
        }
        return res;
    }
};

思路三:动态规划

有点难,下次再来补充

122. 买卖股票的最佳时机 II【中等】

【代码随想录】第10章 贪心算法

题目意思:

  • 只有一只股票!
  • 当前只有买股票或者买股票的操作

思路:把每一题的股价描点画成折线图,求所有上升线段的累加;借鉴376题

  • 贪心:

时间复杂度:O(n)

空间复杂度:O(1)

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

714. 买卖股票的最佳时机含手续费【中等,不会】

【代码随想录】第10章 贪心算法

  • 思路一:贪心

  • 时间复杂度:O(n)

  • 空间复杂度:O(1)

我们在做收获利润操作的时候其实有三种情况:

  • 情况一:收获利润的这一天并不是收获利润区间里的最后一天(不是真正的卖出,相当于持有股票),所以后面要继续收获利润。
  • 情况二:前一天是收获利润区间里的最后一天(相当于真正的卖出了),今天要重新记录最小价格了。
  • 情况三:不作操作,保持原有状态(买入,卖出,不买不卖)
class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int res = 0;
        int minPrice = prices[0]; // 记录最低价格
        for (int i = 1; i < prices.size(); i++) {
            // 情况二:相当于买入
            if (prices[i] < minPrice)  minPrice = prices[i];

            // 情况三:保持原有状态(因为此时买则不便宜,卖则亏本)
            //if (prices[i] >= minPrice && prices[i] <= minPrice + fee) {
            //    continue;
            //}

            // 计算利润,可能有多次计算利润,最后一次计算利润才是真正意义的卖出
            if (prices[i] > minPrice + fee) {
                res += prices[i] - minPrice - fee;
                minPrice = prices[i] - fee; // 情况一,这一步很关键
            }
        }
        return res;
    }
};

当我们卖出一支股票时,我们就立即获得了以相同价格并且免除手续费买入一支股票的权利

  • [x]
class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int buy = prices[0] + fee;
        int profit = 0;
        for (int i = 1; i < prices.size(); ++i) {
            if (prices[i] + fee < buy) {   //更新买入价
                buy = prices[i] + fee;
            }
            else if (prices[i] > buy) {    //收集利润
                profit += prices[i] - buy;
                buy = prices[i];
            }
        }
        return profit;
    }
};

思路二:动态规划

上一篇:【LeetCode】90. 子集 II(错题2刷)


下一篇:Java对IPv6的支持