贪心算法・下篇：区间与字符串大闯关，4 道进阶题解锁高阶玩法

一、贪心算法进阶概述入门篇我们掌握了 “匹配型”“累加型” 的基础贪心进阶篇将聚焦区间调度、字符串分割、环形问题等更复杂的场景。这类题目的贪心策略往往隐藏更深通常需要先对数据排序再通过维护 “当前边界” 来做决策。核心套路是排序定顺序边界做贪心。二、4 道 C 进阶实战例题例 1无重叠区间LeetCode 435题目描述给定一个区间集合找到需要移除区间的最小数量使剩余区间互不重叠。贪心策略按区间的结束位置从小到大排序。每次选择结束最早的区间保留给后续区间留出更多空间这样就能保留最多的不重叠区间移除数量自然最少。cpp运行#include iostream #include vector #include algorithm using namespace std; int eraseOverlapIntervals(vectorvectorint intervals) { if (intervals.empty()) return 0; // 按区间结束位置升序排序 sort(intervals.begin(), intervals.end(), [](const vectorint a, const vectorint b) { return a[1] b[1]; }); int count 1; // 保留的区间数至少保留第一个 int end intervals[0][1]; // 当前最后一个保留区间的结束点 for (int i 1; i intervals.size(); i) { // 当前区间起点 上一个保留区间终点无重叠保留 if (intervals[i][0] end) { end intervals[i][1]; count; } } // 总区间数 - 最多保留数 最少移除数 return intervals.size() - count; } int main() { vectorvectorint intervals {{1,2}, {2,3}, {3,4}, {1,3}}; cout 最少移除区间数 eraseOverlapIntervals(intervals) endl; return 0; }例 2用最少数量的箭引爆气球LeetCode 452题目描述气球在水平数轴上分布每个气球对应一个区间。弓箭从 x 轴垂直射出可以引爆所有覆盖到的气球。求引爆所有气球最少需要多少支箭。贪心策略按气球右边界排序。第一支箭射在第一个气球的最右端尽可能覆盖更多后续气球遇到覆盖不到的气球时新增一支箭并更新射箭位置为当前气球最右端。cpp运行#include iostream #include vector #include algorithm using namespace std; int findMinArrowShots(vectorvectorint points) { if (points.empty()) return 0; // 按右边界升序排序 sort(points.begin(), points.end(), [](const vectorint a, const vectorint b) { return a[1] b[1]; }); int arrows 1; int pos points[0][1]; // 第一支箭的位置 for (int i 1; i points.size(); i) { // 当前气球左边界 射箭位置射不到需要新箭 if (points[i][0] pos) { arrows; pos points[i][1]; // 新箭射在当前气球最右端 } } return arrows; } int main() { vectorvectorint points {{10,16}, {2,8}, {1,6}, {7,12}}; cout 最少需要箭数 findMinArrowShots(points) endl; return 0; }例 3划分字母区间LeetCode 763题目描述把字符串划分为尽可能多的片段同一个字母只出现在其中一个片段里。返回每个片段的长度列表。贪心策略先遍历一次字符串记录每个字母最后一次出现的位置。再遍历字符串不断扩展当前片段的右边界取当前字母最后位置的最大值当遍历到右边界时完成一个片段的分割。cpp运行#include iostream #include vector #include string using namespace std; vectorint partitionLabels(string s) { int last[26] {0}; // 记录每个字母最后出现的下标 for (int i 0; i s.size(); i) { last[s[i] - a] i; } vectorint result; int start 0; // 当前片段起点 int end 0; // 当前片段终点 for (int i 0; i s.size(); i) { // 贪心扩展终点取当前字母最后位置和原终点的较大值 end max(end, last[s[i] - a]); // 遍历到终点完成一个片段 if (i end) { result.push_back(end - start 1); start i 1; // 更新下一个片段起点 } } return result; } int main() { string s ababcbacadefegdehijhklij; vectorint res partitionLabels(s); cout 各片段长度; for (int len : res) cout len ; return 0; }例 4加油站LeetCode 134题目描述环形路线上有n个加油站第i个加油站有汽油gas[i]从第i站开到第i1站消耗汽油cost[i]。判断能否绕环路行驶一周返回出发加油站编号无解返回 - 1。贪心策略总油量 ≥ 总消耗则一定存在解遍历过程中若当前剩余油量为负说明从起点到当前站的所有站都不能作为起点起点直接跳到下一站。cpp运行#include iostream #include vector using namespace std; int canCompleteCircuit(vectorint gas, vectorint cost) { int totalSum 0; // 全程总剩余油量 int curSum 0; // 当前段剩余油量 int start 0; // 起点 for (int i 0; i gas.size(); i) { totalSum gas[i] - cost[i]; curSum gas[i] - cost[i]; // 当前段剩余油量为负说明起点到i都不能作为起点 if (curSum 0) { start i 1; // 起点更新为下一站 curSum 0; // 重置当前段剩余 } } // 总油量不够则无解否则返回起点 return totalSum 0 ? start : -1; } int main() { vectorint gas {1, 2, 3, 4, 5}; vectorint cost {3, 4, 5, 1, 2}; cout 起点加油站编号 canCompleteCircuit(gas, cost) endl; return 0; }谢谢