860.柠檬水找零

题目链接：860.柠檬水找零

class Solution {
public:bool lemonadeChange(vector<int>& bills) {int wallet[2] = {};for (auto& bill : bills) {if (bill == 5) ++wallet[0];if (bill == 10) {if (wallet[0] == 0) {return false;}++wallet[1];--wallet[0];} if (bill == 20) {if (wallet[0] > 0 && wallet[1] > 0) {//先花10--wallet[0];--wallet[1];} else if (wallet[0] >= 3) {//10不够再花5wallet[0] -= 3;} elsereturn false;}}return true;}
};

---

406.根据身高重建队列

题目链接：406.根据身高重建队列
每个人的属性为[h, k]，排列规则为：优先按照h从大到小排列，当h相等时，按照k从小到大排列。
如此排列后，每个人对应的k属性的数值，即为插入的位置。
因为序列容器vector的插入性能较差，因此选择插入成本低的序列容器list来进行插入操作。
最后通过构造函数来实现容器间的相互转换。

class Solution {
public:vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {sort(people.begin(), people.end(),[](const auto& lhs, const auto& rhs) {if (lhs[0] == rhs[0]) return lhs[1] < rhs[1];return lhs[0] > rhs[0];});//比较函数为优先按照h从大到小排列，当h相等时，按照k从小到大排列list<vector<int>> resL;for (auto& someone : people) {int position = someone[1];auto it = resL.begin();while (position--) ++it;resL.insert(it, someone);}return vector<vector<int>>(resL.begin(), resL.end());}
};

std::next 函数的时间复杂度为 $O(1)$，空间复杂度为 $O(1)$。在内存中，std::next 函数只需要存储一个指针即可，因此空间复杂度为 $O(1)$；而对于输入参数it和count，std::next 函数只需要执行一次加法操作和一次取地址操作，因此时间复杂度也是 $O(1)$。

插入部分使用next()函数

class Solution {
public:vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {sort(people.begin(), people.end(),[](const auto& lhs, const auto& rhs) {if (lhs[0] == rhs[0]) return lhs[1] < rhs[1];return lhs[0] > rhs[0];});list<vector<int>> resL;for (auto& someone : people) {resL.insert(next(resL.begin(), someone[1]), someone);}return vector<vector<int>>(resL.begin(), resL.end());}
};

---

452. 用最少数量的箭引爆气球

题目链接：452. 用最少数量的箭引爆气球
思路：处理好相邻的区间的关系，方便统计弓箭的个数。
先排序，按照左边界大小排序后。减少自由度，利于判断。
更新右边界，为了给下一次遍历重叠区间。

class Solution {
public:int findMinArrowShots(vector<vector<int>>& points) {sort(points.begin(), points.end()/*,[](const auto& lhs, const auto& rhs) {return lhs[0] < rhs[0];}*/);int res = 1;for (int i = 1; i < points.size(); ++i) {if (points[i - 1][1] < points[i][0]) {++res;} else {//更新i的右区间，为下一个遍历使用points[i][1] = min(points[i - 1][1], points[i][1]);}}return res;}
};

比较函数可以不写，因为默认就是按照第一个元素由小到大排序的。