數(shù)據(jù)結(jié)構(gòu)與算法之單調(diào)遞增的數(shù)字
單調(diào)遞增的數(shù)字
力扣題目鏈接：https://leetcode-cn.com/problems/monotone-increasing-digits
給定一個(gè)非負(fù)整數(shù) N，找出小于或等于 N 的最大的整數(shù)，同時(shí)這個(gè)整數(shù)需要滿足其各個(gè)位數(shù)上的數(shù)字是單調(diào)遞增。
(當(dāng)且僅當(dāng)每個(gè)相鄰位數(shù)上的數(shù)字 x 和 y 滿足 x <= y 時(shí)，我們稱這個(gè)整數(shù)是單調(diào)遞增的。)
示例 1:
- 輸入: N = 10
- 輸出: 9
示例 2:
- 輸入: N = 1234
- 輸出: 1234
示例 3:
- 輸入: N = 332
- 輸出: 299
說(shuō)明: N 是在 [0, 10^9] 范圍內(nèi)的一個(gè)整數(shù)。
暴力解法
題意很簡(jiǎn)單，那么首先想的就是暴力解法了，來(lái)我替大家暴力一波，結(jié)果自然是超時(shí)!
代碼如下：
- class Solution {
- private:
- bool checkNum(int num) {
- int max = 10;
- while (num) {
- int t = num % 10;
- if (max >= t) max = t;
- else return false;
- num = num / 10;
- }
- return true;
- }
- public:
- int monotoneIncreasingDigits(int N) {
- for (int i = N; i > 0; i--) {
- if (checkNum(i)) return i;
- }
- return 0;
- }
- };
- 時(shí)間復(fù)雜度：O(n * m) m為n的數(shù)字長(zhǎng)度
- 空間復(fù)雜度：O(1)
貪心算法
題目要求小于等于N的最大單調(diào)遞增的整數(shù)，那么拿一個(gè)兩位的數(shù)字來(lái)舉例。
例如：98，一旦出現(xiàn)strNum[i - 1] > strNum[i]的情況(非單調(diào)遞增)，首先想讓strNum[i - 1]--，然后strNum[i]給為9，這樣這個(gè)整數(shù)就是89，即小于98的最大的單調(diào)遞增整數(shù)。
這一點(diǎn)如果想清楚了，這道題就好辦了。
局部最優(yōu)：遇到strNum[i - 1] > strNum[i]的情況，讓strNum[i - 1]--，然后strNum[i]給為9，可以保證這兩位變成最大單調(diào)遞增整數(shù)。
全局最優(yōu)：得到小于等于N的最大單調(diào)遞增的整數(shù)。
但這里局部最優(yōu)推出全局最優(yōu)，還需要其他條件，即遍歷順序，和標(biāo)記從哪一位開(kāi)始統(tǒng)一改成9。
此時(shí)是從前向后遍歷還是從后向前遍歷呢?
從前向后遍歷的話，遇到strNum[i - 1] > strNum[i]的情況，讓strNum[i - 1]減一，但此時(shí)如果strNum[i - 1]減一了，可能又小于strNum[i - 2]。
這么說(shuō)有點(diǎn)抽象，舉個(gè)例子，數(shù)字：332，從前向后遍歷的話，那么就把變成了329，此時(shí)2又小于了第一位的3了，真正的結(jié)果應(yīng)該是299。
所以從前后向遍歷會(huì)改變已經(jīng)遍歷過(guò)的結(jié)果!
那么從后向前遍歷，就可以重復(fù)利用上次比較得出的結(jié)果了，從后向前遍歷332的數(shù)值變化為：332 -> 329 -> 299
確定了遍歷順序之后，那么此時(shí)局部最優(yōu)就可以推出全局，找不出反例，試試貪心。
C++代碼如下：
- class Solution {
- public:
- int monotoneIncreasingDigits(int N) {
- string strNum = to_string(N);
- // flag用來(lái)標(biāo)記賦值9從哪里開(kāi)始
- // 設(shè)置為這個(gè)默認(rèn)值，為了防止第二個(gè)for循環(huán)在flag沒(méi)有被賦值的情況下執(zhí)行
- int flag = strNum.size();
- for (int i = strNum.size() - 1; i > 0; i--) {
- if (strNum[i - 1] > strNum[i] ) {
- flag = i;
- strNum[i - 1]--;
- }
- }
- for (int i = flag; i < strNum.size(); i++) {
- strNum[i] = '9';
- }
- return stoi(strNum);
- }
- };
- 時(shí)間復(fù)雜度：O(n) n 為數(shù)字長(zhǎng)度
- 空間復(fù)雜度：O(n) 需要一個(gè)字符串，轉(zhuǎn)化為字符串操作更方便
總結(jié)
本題只要想清楚個(gè)例，例如98，一旦出現(xiàn)strNum[i - 1] > strNum[i]的情況(非單調(diào)遞增)，首先想讓strNum[i - 1]減一，strNum[i]賦值9，這樣這個(gè)整數(shù)就是89。就可以很自然想到對(duì)應(yīng)的貪心解法了。
想到了貪心，還要考慮遍歷順序，只有從后向前遍歷才能重復(fù)利用上次比較的結(jié)果。
最后代碼實(shí)現(xiàn)的時(shí)候，也需要一些技巧，例如用一個(gè)flag來(lái)標(biāo)記從哪里開(kāi)始賦值9。
其他語(yǔ)言版本
Java：
- 版本1
- class Solution {
- public int monotoneIncreasingDigits(int N) {
- String[] strings = (N + "").split("");
- int start = strings.length;
- for (int i = strings.length - 1; i > 0; i--) {
- if (Integer.parseInt(strings[i]) < Integer.parseInt(strings[i - 1])) {
- strings[i - 1] = (Integer.parseInt(strings[i - 1]) - 1) + "";
- start = i;
- }
- }
- for (int i = start; i < strings.length; i++) {
- strings[i] = "9";
- }
- return Integer.parseInt(String.join("",strings));
- }
- }
java版本1中創(chuàng)建了String數(shù)組，多次使用Integer.parseInt了方法，這導(dǎo)致不管是耗時(shí)還是空間占用都非常高，用時(shí)12ms，下面提供一個(gè)版本在char數(shù)組上原地修改，用時(shí)1ms的版本
- 版本2
- class Solution {
- public int monotoneIncreasingDigits(int n) {
- if (n==0)return 0;
- char[] chars= Integer.toString(n).toCharArray();
- int start=Integer.MAX_VALUE;//start初始值設(shè)為最大值，這是為了防止當(dāng)數(shù)字本身是單調(diào)遞增時(shí)，沒(méi)有一位數(shù)字需要改成9的情況
- for (int i=chars.length-1;i>0;i--){
- if (chars[i]<chars[i-1]){
- chars[i-1]--;
- start=i;
- }
- }
- StringBuilder res=new StringBuilder();
- for (int i=0;i<chars.length;i++){
- if (chars[i]=='0'&&i==0)continue;//防止出現(xiàn)09這樣的情況
- if (i>=start){
- res.append('9');
- }else res.append(chars[i]);
- }
- return Integer.parseInt(res.toString());
- }
- }
Python：
- class Solution:
- def monotoneIncreasingDigits(self, n: int) -> int:
- a = list(str(n))
- for i in range(len(a)-1,0,-1):
- if int(a[i]) < int(a[i-1]):
- a[i-1] = str(int(a[i-1]) - 1)
- a[i:] = '9' * (len(a) - i) #python不需要設(shè)置flag值，直接按長(zhǎng)度給9就好了
- return int("".join(a))
Go
- func monotoneIncreasingDigits(N int) int {
- s := strconv.Itoa(N)//將數(shù)字轉(zhuǎn)為字符串，方便使用下標(biāo)
- ss := []byte(s)//將字符串轉(zhuǎn)為byte數(shù)組，方便更改。
- n := len(ss)
- if n <= 1 {
- return N
- }
- for i:=n-1 ; i>0; i-- {
- if ss[i-1] > ss[i] {//前一個(gè)大于后一位,前一位減1，后面的全部置為9
- ss[i-1] -= 1
- for j := i ; j < n; j++ {//后面的全部置為9
- ss[j] = '9'
- }
- }
- }
- res, _ := strconv.Atoi(string(ss))
- return res
- }
Javascript
- var monotoneIncreasingDigits = function(n) {
- n = n.toString()
- n = n.split('').map(item => {
- return +item
- })
- let flag = Infinity
- for(let i = n.length - 1; i > 0; i--) {
- if(n [i - 1] > n[i]) {
- flag = i
- n[i - 1] = n[i - 1] - 1
- n[i] = 9
- }
- }
- for(let i = flag; i < n.length; i++) {
- n[i] = 9
- }
- n = n.join('')
- return +n
- };
