【贪心算法】day4

📝前言说明：

• 本专栏主要记录本人的贪心算法学习以及LeetCode刷题记录，按专题划分
• 每题主要记录：（1）本人解法 + 本人屎山代码；（2）优质解法 + 优质代码；（3）精益求精，更好的解法和独特的思想（如果有的话）；（4）贪心策略正确性的 “证明”
• 文章中的理解仅为个人理解。如有错误，感谢纠错

🎬个人简介：努力学习ing
📋本专栏：C++刷题专栏
📋其他专栏：C语言入门基础，python入门基础，C++学习笔记，Linux
🎀CSDN主页 愚润泽

你可以点击下方链接，进行其他贪心算法题目的学习

点击链接 开始学习 贪心day1 贪心day2 贪心day3 贪心day4 贪心day5 贪心day6 贪心day7 贪心day8 贪心day9 贪心day10

也可以点击下面连接，学习其他算法

点击链接 开始学习 优选专题 动态规划 递归、搜索与回溯 贪心算法

题目

• 122. 买卖股票的最佳时机 II
• • 个人解
• 1005. K 次取反后最大化的数组和
• • 个人解
• 2418. 按身高排序
• • 个人解

---

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

题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/description/

个人解

思路：

• 拆分成一天一天进行无限次交易
  • 后一天比当前股票便宜就重新买入，比当前股票贵就直接卖出 (贪心策略)
• 细节: 因为可能出现连续递增，所以在卖出后，直接将当天价格作为买入的价格继续贪心
• 其他解法：也可以用一个双指针去找每个上升区间的开始和结束位置，然后添加利润

屎山代码：

class Solution {public: int maxProfit(vector<int>& prices) { int PreMIN = INT_MAX; int ans = 0; for(auto x: prices) { if(x <= PreMIN) PreMIN = x; else { ans += x - PreMIN; PreMIN = x; // 代表未买入状态，同时避免连续递增的股票 } } return ans; }};

时间复杂度：$O(n)$
空间复杂度：$O(1)$

---

1005. K 次取反后最大化的数组和

题目链接：https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/description/

个人解

思路：

• 有点数学题的感觉
  • 先将数组排序
  • 贪心策略:
    1. 从小到大，现将负数取反
    2. 如果没有负数了, 则 k % 2 。（如果结果为 1 ，则将绝对值最小的数取反)

屎山代码：

class Solution {public: int largestSumAfterKNegations(vector<int>& nums, int k) { ranges::sort(nums); int sum = 0; int Min = INT_MAX; for(auto num: nums) { Min = min(Min, abs(num)); if(num < 0 && k > 0) { sum -= num; k--; } else sum += num; } if(k % 2) // 如果还有取反次数，则剩下的一定为非负数了 sum -= 2 * Min; // 把之前加上的减掉 return sum; }};

时间复杂度：$O(nlogn)$
空间复杂度：$O(1)$

---

2418. 按身高排序

题目链接：https://leetcode.cn/problems/sort-the-people/description/

个人解

屎山代码：

class Solution {public: vector<string> sortPeople(vector<string>& names, vector<int>& heights) { int n = names.size(); vector<pair<int, int>> hash; // , 存在vector中，便于后续排序 for(int i = 0; i < n; i++) hash.emplace_back(heights[i], i); ranges::sort(hash.begin(), hash.end(), [](const auto& a, const auto& b){ return a.first > b.first; // 大的优先级高 }); vector<string> ans; for(auto [h, index]: hash) ans.emplace_back(names[index]); return ans; }};

时间复杂度：$O(nlogn)$
空间复杂度：$O(n)$

---

🌈我的分享也就到此结束啦🌈
要是我的分享也能对你的学习起到帮助，那简直是太酷啦！
若有不足，还请大家多多指正，我们一起学习交流！
📢公主，王子：点赞👍→收藏⭐→关注🔍
感谢大家的观看和支持！祝大家都能得偿所愿，天天开心！！！