860. 柠檬水找零

有大的先用大的找零

class Solution {
public:
    // 有大的票子就先花大的票子
    bool lemonadeChange(vector<int>& bills) {
        int cnt1 = 0, cnt2 = 0;
        for (int i = 0; i < bills.size(); i ++)
        {
            if (bills[i] == 5)
            {
                cnt1 ++;
            }
            else if (bills[i] == 10)
            {
                if (cnt1 < 1) return false;
                cnt1 --;
                cnt2 ++;
            }
            else
            {
                if (cnt2 > 0)
                {
                    cnt2 --;
                    cnt1 --;
                    if (cnt2 < 0 || cnt1 < 0) return false;
                }
                else 
                {
                    cnt1 -= 3;
                    if (cnt1 < 0) return false;
                }
            }
        }
        return true;
    }
};

406. 根据身高重建队列

有二维的约束，分看来处理。先按身高从大到小，再依次按第二维插入。

还要注意vector的插入时间复杂度是O(n)，这里可以用链表这个数据结构。

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), [](vector<int>& vec1, vector<int>& vec2)
        {
            if (vec1[0] != vec2[0])
                return vec1[0] > vec2[0];
            return vec1[1] < vec2[1];
        });

        list<vector<int>> res;
        for (int i = 0; i < people.size(); i ++)
        {
            int position = people[i][1];
            auto it = res.begin();
            while (position --)
            {
                it ++;
            }
            res.insert(it, people[i]);
        }

        return vector<vector<int>> (res.begin(), res.end());
    }
};

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

把起点作为分割点

class Solution {
public:
    // 起始的终点作为分界线
    int findMinArrowShots(vector<vector<int>>& points) {
        sort(points.begin(), points.end(), [](vector<int>& vec1, vector<int>& vec2)
        {
            return vec1[1] < vec2[1];
        });

        int res = 0;
        int n = points.size();
        for (int i = 0; i < n; i ++)
        {
            int end = points[i][1]; // 终点
            int j = i + 1;
            while (j < n && points[j][0] <= end) j ++;
            i = j - 1;
            res ++;
        }

        return res;
    }
};