贪心算法在找零、队列重构与区间覆盖问题中的应用
860. 柠檬水找零策略
题目描述：每杯柠檬水售价为5美元。顾客会支付5、10或20美元，你需要现场找零，且初始无任何零钱。若能对每位顾客正确找零，返回true；否则返回false。
关键思路：
- 收到5美元：无需找零，直接计入。
- 收到10美元：需找回一张5美元，若无则失败。
- 收到20美元：优先使用一张10元和一张5元组合（保留更多小额钞票），若不可行，则尝试三张5元。
实现逻辑应优先消耗大额零钱以维持灵活性。
class Solution {
public:
bool canProvideChange(vector<int>& payments) {
int countFive = 0, countTen = 0;
for (int amount : payments) {
if (amount == 5) {
countFive++;
} else if (amount == 10) {
if (countFive == 0) return false;
countFive--;
countTen++;
} else if (amount == 20) {
// 优先使用10+5的组合
if (countTen > 0 && countFive > 0) {
countTen--;
countFive--;
} else if (countFive >= 3) {
countFive -= 3;
} else {
return false;
}
}
}
return true;
}
};
时间复杂度：O(n)，空间复杂度：O(1)。
406. 基于身高和前方人数重建队列
给定二维数组people，其中people[i] = [hi, ki]表示第i个人的身高为hi，其前面有ki个身高大于等于他的人。要求还原出符合条件的队列顺序。
解题策略：
- 先将人群按身高降序排列，若身高相同，则按k值升序排列。
- 遍历排序后的数组，根据每个人的k值将其插入到结果列表的指定位置。
这样可以确保每次插入时，已存在的人都不低于当前人，因此k即为插入位置。
class Solution {
private:
static bool compare(const vector<int>& a, const vector<int>& b) {
if (a[0] != b[0]) return a[0] > b[0];
return a[1] < b[1];
}
public:
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
sort(people.begin(), people.end(), compare);
list<vector<int>> result;
for (const auto& person : people) {
auto it = result.begin();
advance(it, person[1]);
result.insert(it, person);
}
return vector<vector<int>>(result.begin(), result.end());
}
};
使用链表可提升插入效率，避免vector频繁移动元素带来的开销。总时间复杂度为O(n² + n log n)，空间复杂度为O(n)。
452. 最少箭数引爆所有气球
若干气球分布在水平线上，points[i] = [xstart, xend] 表示其横向跨度。一支箭可在任意x坐标垂直射出，并击穿所有包含该坐标的气球。求最少需要多少支箭才能引爆全部气球。
核心思想：合并重叠区间。若两个气球区间相交，则可用同一支箭穿透。
步骤如下：
- 按起始坐标升序排列所有气球。
- 从第二个气球开始遍历，若当前气球起点大于前一个气球的终点，则必须新增一支箭。
- 否则说明存在重叠，更新当前重叠区域的右边界为两者最小值。
class Solution {
public:
int findMinArrows(vector<vector<int>>& intervals) {
if (intervals.empty()) return 0;
sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
return a[0] < b[0];
});
int arrows = 1;
for (int i = 1; i < intervals.size(); ++i) {
if (intervals[i][0] > intervals[i - 1][1]) {
arrows++;
} else {
intervals[i][1] = min(intervals[i][1], intervals[i - 1][1]);
}
}
return arrows;
}
};
时间复杂度主要由排序决定，为O(n log n)；空间复杂度O(1)（忽略递归栈）。
