56. 合并區間 - 力扣（LeetCode）

思路：覆蓋區間問題，先排序再判斷邊界

重點：二維數組可以使用back（）函數直接更換邊界值

class Solution {
public:static bool cmp(const vector<int>& a,const vector<int>& b){return a[0]<b[0];}vector<vector<int>> merge(vector<vector<int>>& intervals) {sort(intervals.begin(),intervals.end(),cmp);vector<vector<int>>ans;int n=intervals.size();ans.push_back(intervals[0]);//第一個區間直接放for(int i=1;i<n;i++){if(ans.back()[1]>=intervals[i][0]){ans.back()[1]=max(ans.back()[1],intervals[i][1]);//更新右邊界}else{ans.push_back(intervals[i]);}}return ans;}
};

738. 單調遞增的數字 - 力扣（LeetCode）

思路：先轉換為字符串，前一個數小于當前數的時候前一個數減一，當前數替換為‘9’

重點：從后向前遍歷使用flag記錄需要替換的下標

class Solution {
public:int monotoneIncreasingDigits(int n) {if(n<=9){return n;}string s=to_string(n);int m=s.size();int flag=m;for(int i=m-1;i>0;i--){if(s[i-1]>s[i]){flag=i;s[i-1]--;}}for(int i=flag;i<m;i++){s[i]='9';}return stoi(s);}
};

總結

貪心算法，需要一定的技巧，覆蓋區間可以直接用back（）函數修改右邊界。修改數字可以使用flag來記錄需要修改的數字的下標