贪心

56. 合并区间 链接：56. 合并区间 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 区间判重，更新 end； 看完题解后的想法 – 实现中遇到的困难 – 代码 class Solution { public: vector<vector<int>> merge(vector<vector<int>>& intervals) { sort(intervals.begin(), intervals.end()); // 核心，先排序 int start = intervals[0][0]; int end = intervals[0][1]; vector<vector<int>> res; for (int i = 1; i < (int)intervals.size(); i++) { int left = intervals[i][0]; int right = intervals[i][1]; if (left <= end) { if (right > end) { end = right; } else { continue; } } else { res.push_back({start, end}); start = left; end = right; } } // 最后一组元素需要手动push res.push_back({start, end}); return res; } }; 738. 单调递增的数字 链接：738. 单调递增的数字 文章：代码随想录 视频：B站讲解 状态：⚠️ 第一想法 第一想法是拿个 vector 把数字都装起来，但是之后怎么做不明白； ...

452. 用最少数量的箭引爆气球 链接：452. 用最少数量的箭引爆气球 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 不断地调整起点和终点范围，如果任意一边（其实是起点，排序之后有序）在范围内，就可以被引爆； 注意如果终点也在范围内就要调整终点位置； 看完题解后的想法 – 实现中遇到的困难 – 代码 class Solution { public: int findMinArrowShots(vector<vector<int>>& points) { sort(points.begin(), points.end()); int sum = 1; int start = points[0][0]; int end = points[0][1]; for (int i = 1; i < points.size(); i++) { if (points[i][0] <= end) { start = points[i][0]; if (points[i][1] <= end) { end = points[i][1]; } } else { start = points[i][0]; end = points[i][1]; sum++; } } return sum; } }; 435. 无重叠区间 链接：435. 无重叠区间 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 跟 LC452 挺像的； ...

134. 加油站 链接：134. 加油站 文章：代码随想录 视频：B站讲解 状态：❌ 第一想法 没想出来； 看完题解后的想法 很巧妙，其实是思维盲区； 既然总油量大于等于总消耗有解，那么只要找到开始盈余的部分，这样剩下的油总能够支持消耗； 这里很巧妙，因为如果总量只要是大于等于，那不管前面亏了多少，后面一定剩了多少，只要不断舍去亏损的位置就行了； 和 LC53 是一个思想； 实现中遇到的困难 – 代码 class Solution { public: int canCompleteCircuit(vector<int>& gas, vector<int>& cost) { int totalDiff = 0; int curDiff = 0; int start = 0; // 1. 如果总油量小于总消耗，不可能跑完 // 2. 既然总油量大于等于总消耗有解，那么就要找到开始盈余的部分，这样才能支撑跑完全程 for (int i = 0; i < gas.size(); i++) { totalDiff += gas[i] - cost[i]; curDiff += gas[i] - cost[i]; if (curDiff < 0) { start = i + 1; curDiff = 0; } } return totalDiff >= 0 ? start : -1; } }; 135. 分发糖果 链接：135. 分发糖果 文章：代码随想录 视频：B站讲解 状态：❌ 第一想法 没啥思路； ...

122. 买卖股票的最佳时机II 链接：122. 买卖股票的最佳时机II 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 连续上涨的利润等于每天差价之和 看完题解后的想法 – 实现中遇到的困难 – 代码 class Solution { public: int maxProfit(vector<int>& prices) { int profit = 0; for (int i = 1; i < prices.size(); i++) { // 只要后一天的股价高于前一天的股价就可以买进卖出，这样一定获利 // 多次交易只是把一段长的收入拆分成了几段小的 if (prices[i] > prices[i - 1]) { profit += prices[i] - prices[i-1]; } } return profit; } }; 55. 跳跃游戏 链接：55. 跳跃游戏 文章：代码随想录 视频：B站讲解 状态：❌ 第一想法 最开始在思考如何到达右边，然后写了一串复杂的判断； 看完题解后的想法 要点不是能不能过去，而是中间会不会断 那么如果某个点的坐标大于了之前所有点的坐标+跨度，就说明这个点到达不了，就断了 所以要维护一个 最大可达坐标 实现中遇到的困难 – 代码 class Solution { public: bool canJump(vector<int>& nums) { int maxReach = 0; for (int i = 0; i < nums.size(); i++) { // 如果当前最大可达坐标小于当前index，说明过不来，错误 if (i > maxReach) { return false; } // 更新当前最大可达坐标，这里的作用就是在这个点之后的点的跨度如果小于该点，也在该点的包括范围内 maxReach = max(maxReach, nums[i] + i); if (maxReach >= nums.size() - 1) { return true; } } return false; } }; 45. 跳跃游戏II 链接：45. 跳跃游戏II 文章：代码随想录 视频：B站讲解 状态：⚠️ 第一想法 可跳区域的左右是否夹了一个更大的可以跳出这个区域的点，如果有就说明可以去这个点，跳到更远的地方； ...

贪心算法理论基础 贪心算法没有固定套路，本质就是选择每一阶段的局部最优，从而达到全局最优。 文章：代码随想录 - 贪心算法理论基础 455. 分发饼干 链接：455. 分发饼干 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 始终用最小可满足的条件去满足匹配； 整体复杂度由排序主导； 看完题解后的想法 – 实现中遇到的困难 – 代码 class Solution { public: int findContentChildren(vector<int>& g, vector<int>& s) { // 排序后贪心 sort(g.begin(), g.end()); sort(s.begin(), s.end()); int index = 0; int res = 0; for (int i = 0; i < g.size(); i++) { while (index < s.size() && s[index] < g[i]) { index++; // 无法满足，skip } if (index < s.size()) { // 满足条件且index合法，分配 res++; index++; // 分配之后也要前进 } } return res; } }; 376. 摆动序列 链接：376. 摆动序列 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 遍历序列，找到每一个拐点；但是很难说清楚为什么这就是最长的； ...