Chapter 11 Greedy Algorithms (2)
基本题目
135. 分发糖果
贪心：两次遍历，分别确定局部递增与递减情况下的糖果数
正确性证明：第一次遍历一定可以确定局部递增。第二次逆向遍历时，取新数值与原数值的较大值，不仅可以保证最终的数值比原数值大（满足可能存在的递增条件），也可以保证比新数值大（满足可能存在的递减条件）。
class Solution {
public:
int candy(vector<int>& ratings) {
int n = ratings.size();
vector<int> candies(n, 1);
for (int i = 1; i < n; i++) {
if (ratings[i] > ratings[i - 1])
candies[i] = candies[i - 1] + 1;
}
int sum = 0;
for (int i = n - 1; i > 0; i--) {
sum += candies[i];
if (ratings[i] < ratings[i - 1])
candies[i - 1] = max(candies[i - 1], candies[i] + 1);
}
return sum + candies[0];
}
};
860. 柠檬水找零
通用解法：从大额到小额找零
class Solution {
public:
bool change(const vector<int> &billValues, vector<int> &billCount, int value) {
int m = billValues.size(), tmp;
for (int i = m - 1; i >= 0; i--) {
tmp = min(billCount[i], value / billValues[i]);
billCount[i] -= tmp;
value -= tmp * billValues[i];
}
return value == 0;
}
bool lemonadeChange(vector<int>& bills) {
vector<int> billValues{5, 10, 20}, billCount{0, 0, 0};
for (const int bill : bills) {
billCount[bill == 10 ? 1 : (bill < 10 ? 0 : 2)]++;
if (!change(billValues, billCount, bill - 5)) return false;
}
return true;
}
};
简单情形：直接讨论
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
int five = 0, ten = 0;
for (const int bill : bills) {
if (bill == 5) five++;
else if (bill == 10) {
if (!five) return false;
five--;
ten++;
}
else {
if (!ten) {
if (five < 3) return false;
five -= 3;
}
else {
if (!five) return false;
five--;
ten--;
}
}
}
return true;
}
};
406. 根据身高重建队列
贪心：先安排身高矮的再安排高的，这样只需要数空位就可以。空位不包含相等元素，因此在初始排序时，相等元素数值更大的在前（从后向前排）
class Solution {
public:
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
sort(people.begin(), people.end(), [](const vector<int> &p1, const vector<int> &p2) {
return p1[0] != p2[0] ? p1[0] < p2[0] : p1[1] > p2[1];
});
vector<vector<int>> result(people.size());
for (const vector<int> p : people) {
int i = -1, count = p[1];
while (count >= 0) {
while (result[++i].size());
count--;
}
result[i] = p;
}
return result;
}
};
也可以先安排身高高的再安排矮的，这样后续插入的人不会影响已插入人的计数，只需要满足新人位置正确即可。对于相等元素，保证数值大的在后插入即可（从前向后排）
452. 用最少数量的箭引爆气球
贪心：按起始坐标排序后，每次只选择有交集的、最多的若干气球一同戳破
正确性证明：若对于连续的气球 a,b,c，若选择跳过 b，那么说明 b 的终止坐标小于 c 的起始坐标，因此这样之后一定会使用单独的一次机会来引爆 b。在这种情况下，b 和 c 一定是分别引爆的，因此让 b 在引爆 a 时一同引爆会取得相同的效果。
class Solution {
public:
int findMinArrowShots(vector<vector<int>>& points) {
sort(points.begin(), points.end());
int count = 0;
int i = 0, n = points.size();
pair<int, int> interval;
while (i < n) {
interval = {points[i][0], points[i][1]};
// Narrow the interval with consecutive balloons
while (interval.first <= interval.second && ++i < n) {
interval.first = max(interval.first, points[i][0]);
interval.second = min(interval.second, points[i][1]);
}
count++;
}
return count;
}
};
另一贪心思路：按终止坐标排序后，每次射剩余气球的最小终止坐标即可，后续跳过已引爆的气球
正确性证明：首先，为了引爆终止坐标最小的气球，显然最好选择最右侧坐标，这是因为选择更小的坐标不可能击中更多气球（已排序）。其次，可以直接将起始坐标不超过上一次射箭坐标的气球直接跳过，这是因为其终止坐标一定大于等于上一次射箭的坐标（否则会基于它选择射箭位置）。
class Solution {
public:
int findMinArrowShots(vector<vector<int>>& points) {
sort(points.begin(), points.end(), [](const vector<int> &p1, const vector<int> &p2) {
return p1[1] < p2[1];
});
int count = 1;
int last = points[0][1];
for (const vector<int> &ballon : points) {
if (ballon[0] <= last) continue;
last = ballon[1];
count++;
}
return count;
}
};
435. 无重叠区间
贪心：按起始点从小到大排序后，依次处理：若终点位于之前的区间内，则使用该区间替代最后的一个，缩小已选择区间的整体范围；若起点位于之前的区间之外，则加入该区间
正确性证明：新加入的区间必然可以替代最后一个选择的区间，这是因为其起点位于后者起点之后。因此只需要考虑何时替代、何时加入即可。
class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
int count = 0, end = INT_MIN;
for (const vector<int> &v : intervals) {
if (v[1] < end) end = v[1];
else if (v[0] >= end) {
end = v[1];
count++;
}
}
return intervals.size() - count;
}
};
贪心算法通用处理手段：从结果反推
- 如何选择第一个区间（最左侧）？选择一个区间终点最小的即可，否则总是可以将它替换。
- 如何选择下一个？忽略区间起点落在所有已选择区间的最大终点左侧的区间（按这种方式选择，其左侧不可能存在完整区间），选择剩余区间中终点最小的。
这种思路与引爆气球的题目十分类似：
- 如何选择第一次引爆的位置？选择范围终点最小的气球，在其右端点发射。该气球必然要被引爆，而位置越靠右就越可能击中更多的气球。
- 如何选择下一个？忽略区间起点落在上一次发射位置左侧的气球（按这种方式发射，其左侧不可能存在气球的左端点），选择剩余气球中终点最小的。
class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end(), [](const vector<int> &v1, const vector<int> &v2) {
return v1[1] < v2[1];
});
int count = 0, end = INT_MIN;
for (const vector<int> &v : intervals) {
if (v[0] >= end) {
end = v[1];
count++;
}
}
return intervals.size() - count;
}
};
763. 划分字母区间
贪心：对于每一个读取到的每一个字母，在其最后一次出现的位置之前，都不会考虑划分
class Solution {
public:
vector<int> partitionLabels(string s) {
int lastAppear[26] = {0};
for (int i = 0; i < s.size(); i++) {
lastAppear[s[i] - 'a'] = i;
}
vector<int> result;
int begin = -1, end = 0;
for (int i = 0; i < s.size(); i++) {
end = max(end, lastAppear[s[i] - 'a']);
if (i == end) {
result.push_back(end - begin);
begin = end;
}
}
return result;
}
};
56. 合并区间
贪心：按区间起点排序后，每次处理下一区间时延申区间长度，直到区间起点未被覆盖
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
vector<vector<int>> result;
int start = intervals[0][0], end = intervals[0][1];
for (const vector<int> &interval : intervals) {
if (interval[0] > end) {
result.push_back({start, end});
start = interval[0];
}
end = max(end, interval[1]);
}
result.push_back({start, end});
return result;
}
};
738. 单调递增的数字
贪心：从低到高比较，若出现非法顺序，则将高位减 1，低位全取 9
class Solution {
public:
int monotoneIncreasingDigits(int n) {
string digits = to_string(n);
int highestWild = digits.size();
for (int i = digits.size() - 2; i >= 0; i--) {
if (digits[i] > digits[i + 1]) {
digits[i]--;
highestWild = i;
}
}
for (int i = digits.size() - 1; i > highestWild; i--) {
digits[i] = '9';
}
return stoi(digits);
}
};
968. 监控二叉树
贪心思想：叶子节点放监控是浪费的，永远都应当选择叶子节点的父节点（父节点与叶子节点显然需要二选一）。以此为基础，向上递归即可，传递节点的状态
class Solution {
public:
int minCameraCover(TreeNode* root) {
int result = 0;
if (!solve(root, result)) result++;
return result;
}
int solve(TreeNode *root, int &result) {
if (!root) return 2; // leaf node would return 0 in this way
// State is returned: 0-Uncovered, 1-Selected, 2-Covered
int left = solve(root->left, result);
int right = solve(root->right, result);
if (left == 0 || right == 0) {
result++;
return 1;
}
if (left == 1 || right == 1) return 2;
return 0;
}
};