1.一开始的思路为先将整个int的每一位数提取出来然后寻找其中的最小值min如果最小值的位置不在最高位那么最大的数字一定是以min为最高位、相同数量级的数减1。如果在最高位那么最高位肯定是min之后寻找下一个较小位在这之间的位数填充为新的min。初步写出的代码如下1. int monotoneIncreasingDigits(int n) { 2. int num[10] {0}; 3. int start 9; 4. while (n ! 0){ 5. num[start--] n % 10; 6. n / 10; 7. } 8. start; 9. 10. int min_idx 0; 11. int min INT_MAX; 12. int hash[10] {0}; 13. for (int i start; i 10; i){ 14. if (min num[i]){ 15. min num[i]; 16. min_idx i - start; 17. hash[num[i]] i - start; 18. } 19. } 20. 21. int res; 22. if (min_idx ! 0){ 23. res (int)pow(10, 9 - start) * (min 1) - 1; 24. } else { 25. res min; 26. int end; 27. while (min 8 hash[min] 0); 28. end hash[min]; 29. 30. for (int i 1; i 10 - start; i){ 31. if (i end){ 32. res res * 10 min; 33. } else { 34. while (min 8 hash[min] 0); 35. end hash[min]; 36. } 37. } 38. } 39. 40. return res; 41. }但该代码是不正确的本地算例都没有通过。2.发现自己被题目中举的“1234”的例子迷惑了以“1432”为例最小数应该是“1399”并不是与第二个最小值之间填充最小值。正确的做法是寻找第一个波峰的位置记录出现该波峰的第一个下标排除连续的重复位数之后将该下标位置的数值减1后面的数字全部置为9即可。3.基于以上思想写出的完整代码如下1. int monotoneIncreasingDigits(int n) { 2. // 输入数字为0直接返回0 3. if (n 0) return 0; 4. 5. // num数组存储数字每一位int最大10位足够初始全0 6. int num[10] {0}; 7. int start 9; 8. // 逐位拆分n低位存数组右侧高位存左侧 9. while (n ! 0){ 10. num[start--] n % 10; 11. n / 10; 12. } 13. // start修正为数字最高位所在下标 14. start; 15. 16. int cur start 1; 17. // first记录最后一次出现数字上升的位置 18. int first start; 19. while (cur 10){ 20. // 当前位 前一位满足单调不减规则 21. if (num[cur] num[cur - 1]){ 22. // 当前位严格大于前一位更新上升标记位置 23. if (num[cur] num[cur - 1]){ 24. first cur; 25. } 26. cur; 27. } 28. // 出现当前位 前一位破坏单调递增需要修正 29. else { 30. // 最后上升位数字减1 31. num[first]--; 32. // 该位置之后全部置9先把指针跳到下一位 33. cur first 1; 34. break; 35. } 36. } 37. 38. // first下标右侧所有数字统一赋值为9保证数字尽可能大 39. while (cur 10){ 40. num[cur] 9; 41. } 42. 43. // 将数组中有效数字重新拼接成最终整数 44. int res num[start]; 45. for (int i start 1; i 10; i){ 46. res res * 10 num[i]; 47. } 48. return res; 49. }该算法时间复杂度为O(logn)空间复杂度为O(logn)n表示输入数字的位数。4.该算法一开始提取每一位数值的时候用的循环判断条件是n ! 0需要注意输入的n就等于0的特殊情况。
1.一开始的思路为先将整个int的每一位数提取出来然后寻找其中的最小值min如果最小值的位置不在最高位那么最大的数字一定是以min为最高位、相同数量级的数减1。如果在最高位那么最高位肯定是min之后寻找下一个较小位在这之间的位数填充为新的min。初步写出的代码如下1. int monotoneIncreasingDigits(int n) { 2. int num[10] {0}; 3. int start 9; 4. while (n ! 0){ 5. num[start--] n % 10; 6. n / 10; 7. } 8. start; 9. 10. int min_idx 0; 11. int min INT_MAX; 12. int hash[10] {0}; 13. for (int i start; i 10; i){ 14. if (min num[i]){ 15. min num[i]; 16. min_idx i - start; 17. hash[num[i]] i - start; 18. } 19. } 20. 21. int res; 22. if (min_idx ! 0){ 23. res (int)pow(10, 9 - start) * (min 1) - 1; 24. } else { 25. res min; 26. int end; 27. while (min 8 hash[min] 0); 28. end hash[min]; 29. 30. for (int i 1; i 10 - start; i){ 31. if (i end){ 32. res res * 10 min; 33. } else { 34. while (min 8 hash[min] 0); 35. end hash[min]; 36. } 37. } 38. } 39. 40. return res; 41. }但该代码是不正确的本地算例都没有通过。2.发现自己被题目中举的“1234”的例子迷惑了以“1432”为例最小数应该是“1399”并不是与第二个最小值之间填充最小值。正确的做法是寻找第一个波峰的位置记录出现该波峰的第一个下标排除连续的重复位数之后将该下标位置的数值减1后面的数字全部置为9即可。3.基于以上思想写出的完整代码如下1. int monotoneIncreasingDigits(int n) { 2. // 输入数字为0直接返回0 3. if (n 0) return 0; 4. 5. // num数组存储数字每一位int最大10位足够初始全0 6. int num[10] {0}; 7. int start 9; 8. // 逐位拆分n低位存数组右侧高位存左侧 9. while (n ! 0){ 10. num[start--] n % 10; 11. n / 10; 12. } 13. // start修正为数字最高位所在下标 14. start; 15. 16. int cur start 1; 17. // first记录最后一次出现数字上升的位置 18. int first start; 19. while (cur 10){ 20. // 当前位 前一位满足单调不减规则 21. if (num[cur] num[cur - 1]){ 22. // 当前位严格大于前一位更新上升标记位置 23. if (num[cur] num[cur - 1]){ 24. first cur; 25. } 26. cur; 27. } 28. // 出现当前位 前一位破坏单调递增需要修正 29. else { 30. // 最后上升位数字减1 31. num[first]--; 32. // 该位置之后全部置9先把指针跳到下一位 33. cur first 1; 34. break; 35. } 36. } 37. 38. // first下标右侧所有数字统一赋值为9保证数字尽可能大 39. while (cur 10){ 40. num[cur] 9; 41. } 42. 43. // 将数组中有效数字重新拼接成最终整数 44. int res num[start]; 45. for (int i start 1; i 10; i){ 46. res res * 10 num[i]; 47. } 48. return res; 49. }该算法时间复杂度为O(logn)空间复杂度为O(logn)n表示输入数字的位数。4.该算法一开始提取每一位数值的时候用的循环判断条件是n ! 0需要注意输入的n就等于0的特殊情况。
)
