贪心算法

1.买卖股票的最佳时机

买卖股票的最佳时机
买的那天一定是卖的那天之前的最小值。 每到一天，维护那天之前的最小值即可。
在题目中，我们只要用
一个变量记录一个历史最低价格 minprice，我们就可以假设自己的股票是在那天买的。
那么我们在第 i 天卖出股票能得到的利润就是 prices[i] - minprice，更新利润最大值。

class Solution {
public:int maxProfit(vector<int>& prices) {int min_prices = INT_MAX;int ans = 0;for (auto &p: prices) {min_prices = min(min_prices, p);ans = max(ans, p - min_prices);}return ans;}
};

2.跳跃游戏

跳跃游戏
我们依次遍历数组中的每一个位置，并实时维护最远可以到达的位置。对于当前遍历到的位置 x，如果它在最远可以到达的位置的范围内，那么我们就可以从起点通过若干次跳跃到达该位置，因此我们可以用 x+nums[x] 更新最远可以到达的位置。

在遍历的过程中，如果最远可以到达的位置大于等于数组中的最后一个位置，那就说明最后一个位置可达，我们就可以直接返回 True 作为答案。反之，如果在遍历结束后，最后一个位置仍然不可达，我们就返回 False 作为答案。

class Solution {
public:bool canJump(vector<int>& nums) {int n = nums.size();//最远能到达距离，最开始为0int rightmost = 0;for (int i = 0; i < n; i++) {//当前位置在最远能到达距离内if (i <= rightmost) {//更新最远能到达举例，i + nums[i]是当前位置能到的最远距离rightmost = max(rightmost, i + nums[i]);//如果说能到最后一个元素的位置则为trueif (rightmost >= n - 1) {return true;}}}return false;}
};

3.跳跃游戏 II

跳跃游戏 II
与上题相比，我们需要增加一个变量end，记录上一次跳跃能到的最远边界，比如下图，从下标0出发，我们第一跳能够到达的最远位置为下标2，跳跃次数+1，下标1和下标2记录最远能够到达的下标就是max(1+3, 2+1) = 4。也就是说我们两跳最远能到达下标4。
我们维护当前能够到达的最大下标位置，记为边界。我们从左到右遍历数组，到达边界时，更新边界并将跳跃次数增加1。
在遍历数组时，我们不访问最后一个元素，这是因为在访问最后一个元素之前，我们的边界一定大于等于最后一个位置，否则就无法跳到最后一个位置了。如果访问最后一个元素，在边界正好为最后一个位置的情况下，我们会增加一次「不必要的跳跃次数」，因此我们不必访问最后一个元素。
可以这么理解 想象你在玩大富翁，回合制游戏，随身带的钱决定你每回合最多可以走多少格，需要以最短的回合数到达终点。 格子里面的数字代表“钱”，每回合你需要停留在格子里休息得到补充的“钱”才能继续行走。 每次走到一个格子的时候，你需要估计预算在下一个回合能走多少格，哪个格子的钱最多，下一回合就去那个格子 。但是前面的格子里有多少钱有战争迷雾看不到，要到了才知道。 end指本回合能走的最远位置，即钱用完了就不能继续往前了，rightmost就是钱。

class Solution {
public:int jump(vector<int>& nums) {//能跳到的最远位置int rightmost = 0;//跳跃次数int lessjump = 0;//上次跳跃可达最远右边界int end = 0;for (int i = 0; i < nums.size() - 1; i++) {if (i <= rightmost) {rightmost = max(rightmost, i + nums[i]);//到上次跳跃能到的最远右边界了if (i == end) {//这次跳跃能到的最远右边界end = rightmost;//跳跃次数+1lessjump++;}}}return lessjump;       }
};

4.划分字母区间

划分字母区间
想切割，要有首尾两个指针，确定了结尾指针，就能确定下一个切割的开始指针。
遍历字符串，如果已扫描部分的所有字符，都只出现在已扫描的范围内，即可做切割。
下图已扫描的绿色字符，对应的最远位置，都不超过 8，在 8 这切一刀，[0:8]的字符都不会出现在别处。

这道题相当于前两道跳跃题，遍历字符串，记录当前能跳到的最远距离。

class Solution {
public:vector<int> partitionLabels(string s) {vector<int> ans;unordered_map<char, int> mp;//记录当前字母出现的最远距离for (int i = 0; i < s.length(); i++) {mp[s[i]] = i;}int right = 0, left = 0;for (int i = 0; i < s.length(); i++) {//更新跳跃的最远距离right = max(right, mp[s[i]]);//跳到最远距离了if (i == right) {//记录长度ans.push_back(right - left + 1);//从下一个元素重新开始left = i + 1;}}return ans;}
};

区间合并

1.合并区间

56. 合并区间
这道题就是比较当前vector.back()[1]和下一个vector, [0]的大小，如果有重叠则更新vector.back()[1]。

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {vector<vector<int>> res;//先按左端点排序sort(intervals.begin(), intervals.end());for (int i = 0; i < intervals.size(); i++) {//记录当前区间的L、R值int L = intervals[i][0], R = intervals[i][1];//如果是第一个区间，或者说相邻区间没有重叠if (res.empty() || res.back()[1] < L) {//添加当前区间res.push_back({L, R});} else {//否则更新区间的右端点res.back()[1] = max(res.back()[1], R);}}return res;}
};