56. 合并区间
给出一个区间的集合，请合并所有重叠的区间。
class Solution {
public:
static bool cmp(const vector<int>& A, const vector<int>& B){
if(A[0]!=B[0]) return A[0]<B[0];
return A[1]<B[1];
}
vector<vector<int>> merge(vector<vector<int>>& intervals) {
vector<vector<int>> result;
if(intervals.size()==0) return result;
sort(intervals.begin(), intervals.end(), cmp);
for(int i=1; i<intervals.size(); i++){
if(intervals[i][0]<=intervals[i-1][1]){
intervals[i][0] = intervals[i-1][0];
intervals[i][1] = max(intervals[i-1][1], intervals[i][1]);
}else{
result.push_back(intervals[i-1]);
}
}
result.push_back(intervals[intervals.size()-1]);
return result;
}
};- 时间复杂度: O(nlogn)
- 空间复杂度: O(logn)，排序需要的空间开销
738.单调递增的数字
给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。
举一个例子，98，一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增），首先想让strNum[i - 1]--，然后strNum[i]给为9，这样这个整数就是89，即小于98的最大的单调递增整数。
需要从前往后遍历还是从后往前呢？
从前向后遍历的话，遇到strNum[i - 1] > strNum[i]的情况，让strNum[i - 1]减一，但此时如果strNum[i - 1]减一了，可能又小于strNum[i - 2]。比如332从前往后会变成329，但这个时候2又小于3了。
那么从后向前遍历，就可以重复利用上次比较得出的结果了，从后向前遍历332的数值变化为：332 -> 329 -> 299。
注意使用int to string用‘to_string’，string to int用‘stoi’。
class Solution {
public:
int monotoneIncreasingDigits(int n) {
string str = to_string(n);
int flag = str.size();
for(int i=str.size()-1; i>0; i--){
if(str[i-1]>str[i]){
flag = i;
str[i-1]--;
}
}
for(int i=flag; i<str.size();i++){
str[i] = '9';
}
return stoi(str);
}
};- 时间复杂度：O(n)，n 为数字长度
- 空间复杂度：O(n)，需要一个字符串，转化为字符串操作更方便
总结
两个维度权衡问题
在出现两个维度相互影响的情况时，两边一起考虑一定会顾此失彼，要先确定一个维度，再确定另一个一个维度。
在讲解本题的过程中，还强调了编程语言的重要性，模拟插队的时候，使用C++中的list（链表）替代了vector(动态数组)，效率会高很多。
贪心解决区间问题
重点是在排序+去重