力扣hot100——贪心

121. 买卖股票的最佳时机

class Solution {
public:int maxProfit(vector<int>& a) {if (a.size() == 1) return 0;int ans = 0;int mi = a[0];for (int i = 1; i < a.size(); i++) {ans = max(ans, a[i] - mi);mi = min(mi, a[i]);}return ans;}
};

55. 跳跃游戏

class Solution {
public:bool canJump(vector<int>& a) {int r = 0;for (int i = 0; i < a.size(); i++) {if (r < i) return false;r = max(r, i + a[i]);}return true;}
};

45. 跳跃游戏 II

class Solution {
public:int jump(vector<int>& a) {int r = 0;int mx = 0;int ans = 0;for (int i = 0; i < a.size() - 1; i++) {mx = max(mx, i + a[i]);if (i == r) {ans++;r = mx;}}return ans;}
};

贪心， 求最小的覆盖区间，以至于覆盖所有区间

注意题目保证了一定可以到达，并且考虑边界情况，只需到到size - 2位置就行

 763. 划分字母区间

class Solution {
public:vector<int> partitionLabels(string s) {map<char, pair<int, int>> mp;for (int i = 0; i < s.size(); i++) {if (!mp.count(s[i])) mp[s[i]] = { i, i };else mp[s[i]].second = i;}vector<pair<int, int>> v;for (auto [x, y] : mp) v.push_back(y);sort(v.begin(), v.end());int l = 0;int r = 0;vector<int> ans;for (int i = 0; i < v.size(); i++) {if (v[i].first > r) {ans.push_back(r - l + 1);l = v[i].first;}r = max(r, v[i].second);}ans.push_back(r - l + 1);return ans;}
};

区间合并典题：求出同种字符的最大覆盖区间，合并区间即可