LeetCode 37天 | 738.单调递增的数字 贪心算法总结

738. 单调递增的数字
今天就做一题，监控二叉树不想做了。从后向前找到最终的一个前大于后的情况，记录后为修改起点，前为减一操作，后面都可以为9，因此前仅减一就可以了。

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        int res;
        // int to string 的函数to_string() 可以把整数转化为字符串
        string num = to_string(n);
        // 标记修改字符串的起始位置
        int flag = num.size();
        // 从后往前遍历，找到最后一个前大于后的点，前点减一，后点标记下来
        for (int i = num.size()-1; i>0; i--) {
            if (num[i-1] > num[i]) {
                flag = i;
                num[i-1]--;
            }
        }
        // 从标记点开始将字符赋值为9
        for (int i = flag; i<num.size(); i++) {
            num[i] = '9';
        }
        // 字符串转化为int类型
        res = stoi(num);
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24