# 加油站

题目链接🔗

# 思路一

直接对全局进行贪心选择：

情况一：如果 gas 的总和小于 cost 总和，那么无论从哪里出发，一定是跑不了一圈的
情况二：rest [i] = gas [i]-cost [i] 为一天剩下的油，i 从 0 开始计算累加到最后一站，如果累加没有出现负数，说明从 0 出发，油就没有断过，那么 0 就是起点。
情况三：如果累加的最小值是负数，汽车就要从非 0 节点出发，从后向前，看哪个节点能把这个负数填平，能把这个负数填平的节点就是出发节点。

	class Solution {
	public:
	int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
	int curSum = 0;
	int min = INT_MAX; // 从起点出发，油箱里的油量最小值
	for (int i = 0; i < gas.size(); i++) {
	int rest = gas[i] - cost[i];
	curSum += rest;
	if (curSum < min) {
	min = curSum;
	}
	}
	if (curSum < 0) return -1; // 情况 1
	if (min >= 0) return 0; // 情况 2
	// 情况 3
	for (int i = gas.size() - 1; i >= 0; i--) {
	int rest = gas[i] - cost[i];
	min += rest;
	if (min >= 0) {
	return i;
	}
	}
	return -1;
	}
	};

首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明各个站点的加油站剩油量 rest [i] 相加一定是大于等于零的。

每个加油站的剩余量 rest [i] 为 gas [i] - cost [i]。

i 从 0 开始累加 rest [i]，和记为 curSum，一旦 curSum 小于零，说明 [0, i] 区间都不能作为起始位置，因为这个区间选择任何一个位置作为起点，到 i 这里都会断油，那么起始位置从 i+1 算起，再从 0 计算 curSum。

Alt text

局部最优：当前累加 rest [i] 的和 curSum 一旦小于 0，起始位置至少要是 i+1，因为从 i 之前开始一定不行。

全局最优：找到可以跑一圈的起始位置。

	class Solution {
	public:
	int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
	int curSum = 0;
	int totalSum = 0;
	int start = 0;
	for (int i = 0; i < gas.size(); i++) {
	curSum += gas[i] - cost[i];
	totalSum += gas[i] - cost[i];
	if (curSum < 0) { // 当前累加 rest [i] 和 curSum 一旦小于 0
	start = i + 1; // 起始位置更新为 i+1
	curSum = 0; //curSum 从 0 开始
	}
	}
	if (totalSum < 0) return -1; // 说明怎么走都不可能跑一圈了
	return start;
	}
	};

本题采用了两次贪心的策略：

此时局部最优：只要右边评分比左边大，右边的孩子就多一个糖果。全局最优：相邻的孩子中，评分高的右孩子获得比左边孩子更多的糖果。

此时局部最优：取 candyVec [i + 1] + 1 和 candyVec [i] 最大的糖果数量，保证第 i 个小孩的糖果数量既大于左边的也大于右边的。全局最优：相邻的孩子中，评分高的孩子获得更多的糖果。

这样从局部最优推出了全局最优，即：相邻的孩子中，评分高的孩子获得更多的糖果。

Alt text

	class Solution {
	public:
	int candy(vector<int>& ratings) {
	vector<int> candyVec(ratings.size(), 1);
	// 从前向后
	for (int i = 1; i < ratings.size(); i++) {
	if (ratings[i] > ratings[i - 1]) candyVec[i] = candyVec[i - 1] + 1;
	}
	// 从后向前
	for (int i = ratings.size() - 2; i >= 0; i--) {
	if (ratings[i] > ratings[i + 1] ) {
	candyVec[i] = max(candyVec[i], candyVec[i + 1] + 1);
	}
	}
	// 统计结果
	int result = 0;
	for (int i = 0; i < candyVec.size(); i++) result += candyVec[i];
	return result;
	}
	};

题目链接🔗

有如下三种情况：

因为美元 10 只能给账单 20 找零，而美元 5 可以给账单 10 和账单 20 找零，美元 5 更万能！

所以局部最优：遇到账单 20，优先消耗美元 10，完成本次找零。全局最优：完成全部账单的找零。

	class Solution {
	public:
	bool lemonadeChange(vector<int>& bills) {
	int five = 0, ten = 0, twenty = 0;
	for (int bill : bills) {
	// 情况一
	if (bill == 5) five++;
	// 情况二
	if (bill == 10) {
	if (five <= 0) return false;
	ten++;
	five--;
	}
	// 情况三
	if (bill == 20) {
	// 优先消耗 10 美元，因为 5 美元的找零用处更大，能多留着就多留着
	if (five > 0 && ten > 0) {
	five--;
	ten--;
	} else if (five >= 3) {
	five -= 3;
	} else return false;
	}
	}
	return true;
	}
	};

题目链接🔗

h 和 k 两个维度，先确定一个维度 h，就是身高。前面的节点一定比本节点高，让高个子在前面。

之后只需要按照 k 为下标重新插入队列就可以了。

Alt text

局部最优：优先按身高高的 people 的 k 来插入。插入操作过后的 people 满足队列属性。

全局最优：最后都做完插入操作，整个队列满足题目队列属性。

	class Solution {
	public:
	// 身高从大到小排（身高相同 k 小的站前面）
	static bool cmp(const vector<int>& a, const vector<int>& b) {
	if (a[0] == b[0]) return a[1] < b[1];
	return a[0] > b[0];
	}
	vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
	sort(people.begin(), people.end(), cmp);
	list<vector<int>> que; //list 底层是链表实现，插入效率比 vector 高的多
	for (int i = 0; i < people.size(); i++) {
	int position = people[i][1]; // 插入到下标为 position 的位置
	std::list<vector<int>>::iterator it = que.begin();
	while (position--) { // 寻找在插入位置
	it++;
	}
	que.insert(it, people[i]);
	}
	return vector<vector<int>>(que.begin(), que.end());
	}
	};