上海自适应网站,关键词推广哪家好,wordpress 网站搭建,网络设计师工资给定一个非负整数 N#xff0c;找出小于或等于 N 的最大的整数#xff0c;同时这个整数需要满足其各个位数上的数字是单调递增。
#xff08;当且仅当每个相邻位数上的数字 x 和 y 满足 x y 时#xff0c;我们称这个整数是单调递增的。#xff09;
示例 1:
输入: …给定一个非负整数 N找出小于或等于 N 的最大的整数同时这个整数需要满足其各个位数上的数字是单调递增。
当且仅当每个相邻位数上的数字 x 和 y 满足 x y 时我们称这个整数是单调递增的。
示例 1:
输入: N 10 输出: 9 示例 2:
输入: N 1234 输出: 1234 示例 3:
输入: N 332 输出: 299 说明: N 是在 [0, 10^9] 范围内的一个整数。
思路
如果a[i]一直大于等于a[i-1]直接输出就好
如果不是需要判断主要分两种情况
1.如果a[i]a[i-1]并且a[i-1]a[i-2]则a[i-1]-1后面的都变为9
例如123453-123449
2.如果a[i]a[i-1]并且a[i-1]a[i-2],则一直向前遍历直到a[k]!a[i-1]然后a[k]-1,h后面的都变为9
例如123332-122999
提交的代码
class Solution { public int monotoneIncreasingDigits(int N) { int t,sum0,i0,n1,b; int a[] new int[12]; t N; while(t!0) { t t/10; i; } t N; bi; while(t!0) { a[i-1] t%10; t t/10; i--; } t0; sum a[0]; for(i 0;ib;i) { if(i0) { if(a[i]a[i-1]) { sum sum*10a[i]; if(a[i]a[i-1]) { n; //n用来记录有多少个连续相同的数字 } else { n1; } continue; } else { while(n!0) { sum sum-a[i-1-t]; sum sum/10; t; n--; //System.out.println(sum); } a[i-t] a[i-t] - 1; sum sum*10a[i-t]; // System.out.println(sum); for(int ji-t1;jb;j) { a[j] 9; sum sum*10a[j]; } break; } } } return sum; }
}
