【贪心算法】day4
📝前言说明：
- 本专栏主要记录本人的贪心算法学习以及LeetCode刷题记录，按专题划分
- 每题主要记录：（1）本人解法 + 本人屎山代码；（2）优质解法 + 优质代码；（3）精益求精，更好的解法和独特的思想（如果有的话）；（4）贪心策略正确性的 “证明”
- 文章中的理解仅为个人理解。如有错误，感谢纠错
🎬个人简介：努力学习ing
📋本专栏：C++刷题专栏
📋其他专栏：C语言入门基础，python入门基础，C++学习笔记，Linux
🎀ZEEKLOG主页 愚润泽
你可以点击下方链接，进行其他贪心算法题目的学习
| 点击链接 | 开始学习 |
|---|---|
| 贪心day1 | 贪心day2 |
| 贪心day3 | 贪心day4 |
| 贪心day5 | 贪心day6 |
| 贪心day7 | 贪心day8 |
| 贪心day9 | 贪心day10 |
也可以点击下面连接，学习其他算法
| 点击链接 | 开始学习 |
|---|---|
| 优选专题 | 动态规划 |
| 递归、搜索与回溯 | 贪心算法 |
题单获取→ 【贪心算法】题单汇总
题目
122. 买卖股票的最佳时机 II
题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/description/
个人解
思路：
- 拆分成一天一天进行无限次交易
- 后一天比当前股票便宜就重新买入，比当前股票贵就直接卖出 (贪心策略)
- 细节: 因为可能出现连续递增，所以在卖出后，直接将当天价格作为买入的价格继续贪心
- 其他解法：也可以用一个双指针去找每个上升区间的开始和结束位置，然后添加利润
屎山代码：
classSolution{public:intmaxProfit(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(n) O(n)
空间复杂度： O ( 1 ) O(1) O(1)
1005. K 次取反后最大化的数组和
题目链接：https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/description/
个人解
思路：
- 有点数学题的感觉
- 先将数组排序
- 贪心策略:
- 从小到大，现将负数取反
- 如果没有负数了, 则
k % 2。（如果结果为1，则将绝对值最小的数取反)
屎山代码：
classSolution{public:intlargestSumAfterKNegations(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 ( n l o g n ) O(nlogn) O(nlogn)
空间复杂度： O ( 1 ) O(1) O(1)
2418. 按身高排序
题目链接：https://leetcode.cn/problems/sort-the-people/description/
个人解
屎山代码：
classSolution{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(),[](constauto& a,constauto& b){return a.first > b.first;// 大的优先级高}); vector<string> ans;for(auto[h, index]: hash) ans.emplace_back(names[index]);return ans;}};时间复杂度： O ( n l o g n ) O(nlogn) O(nlogn)
空间复杂度： O ( n ) O(n) O(n)
🌈我的分享也就到此结束啦🌈
要是我的分享也能对你的学习起到帮助，那简直是太酷啦！
若有不足，还请大家多多指正，我们一起学习交流！
📢公主，王子：点赞👍→收藏⭐→关注🔍
感谢大家的观看和支持！祝大家都能得偿所愿，天天开心！！！
