- 1. 分配饼干
- 2. 不重叠区间个数
- 3. 投飞镖刺破气球
- 5. 买卖股票最大的收益
- 6. 买卖股票的最大收益 II
- 9. 修改一个数成为非递减数组
- 10. 子数组的最大和
- 11. 分隔字符串使同种字符出现在一起
保证每次操作都是局部最优的，并且最后得到的结果是全局最优的。
1. 分配饼干
Input: grid[1,3], size[1,2,4]
Output: 2
2. 不重叠区间个数
- Non-overlapping Intervals (Medium)
题目描述：计算让一组区间不重叠所需要移除的区间个数。
在每次选择中，区间的结尾最为重要，选择的区间结尾越小，留给后面的区间的空间越大，那么后面能够选择的区间个数也就越大。
按区间的结尾进行排序，每次选择结尾最小，并且和前一个区间不重叠的区间。
3. 投飞镖刺破气球
- Minimum Number of Arrows to Burst Balloons (Medium)
Input:
[[10,16], [2,8], [1,6], [7,12]]Output:
2
题目描述：气球在一个水平数轴上摆放，可以重叠，飞镖垂直投向坐标轴，使得路径上的气球都被刺破。求解最小的投飞镖次数使所有气球都被刺破。
也是计算不重叠的区间个数，不过和 Non-overlapping Intervals 的区别在于，[1, 2] 和 [2, 3] 在本题中算是重叠区间。
5. 买卖股票最大的收益
- Best Time to Buy and Sell Stock (Easy)
题目描述：一次股票交易包含买入和卖出，只进行一次交易，求最大收益。
只要记录前面的最小价格，将这个最小价格作为买入价格，然后将当前的价格作为售出价格，查看当前收益是不是最大收益。
6. 买卖股票的最大收益 II
- Best Time to Buy and Sell Stock II (Easy)
题目描述：可以进行多次交易，多次交易之间不能交叉进行，可以进行多次交易。
对于 [a, b, c, d]，如果有 a <= b <= c <= d ，那么最大收益为 d - a。而 d - a = (d - c) + (c - b) + (b - a) ，因此当访问到一个 prices[i] 且 prices[i] - prices[i-1] > 0，那么就把 prices[i] - prices[i-1] 添加到收益中。
9. 修改一个数成为非递减数组
题目描述：判断一个数组是否能只修改一个数就成为非递减数组。
在出现 nums[i] < nums[i - 1] 时，需要考虑的是应该修改数组的哪个数，使得本次修改能使 i 之前的数组成为非递减数组，并且 不影响后续的操作 。优先考虑令 nums[i - 1] = nums[i]，因为如果修改 nums[i] = nums[i - 1] 的话，那么 nums[i] 这个数会变大，就有可能比 nums[i + 1] 大，从而影响了后续操作。还有一个比较特别的情况就是 nums[i] < nums[i - 2]，修改 nums[i - 1] = nums[i] 不能使数组成为非递减数组，只能修改 nums[i] = nums[i - 1]。题目描述：判断一个数组是否能只修改一个数就成为非递减数组。
在出现 nums[i] < nums[i - 1] 时，需要考虑的是应该修改数组的哪个数，使得本次修改能使 i 之前的数组成为非递减数组，并且 不影响后续的操作 。优先考虑令 nums[i - 1] = nums[i]，因为如果修改 nums[i] = nums[i - 1] 的话，那么 nums[i] 这个数会变大，就有可能比 nums[i + 1] 大，从而影响了后续操作。还有一个比较特别的情况就是 nums[i] < nums[i - 2]，修改 nums[i - 1] = nums[i] 不能使数组成为非递减数组，只能修改 nums[i] = nums[i - 1]。
if (i - 2 >= 0 && nums[i - 2] > nums[i]) {
nums[i] = nums[i - 1];
} else {
nums[i - 1] = nums[i];
}