給你一個整數 num 。你可以對它進行以下步驟共計 兩次：

選擇一個數字 x (0 <= x <= 9).
選擇另一個數字 y (0 <= y <= 9) 。
數字 y 可以等于 x 。
將 num中所有出現 x 的數位都用 y 替換。
令兩次對 num 的操作得到的結果分別為 a 和 b 。
請你返回 a 和 b 的 最大差值 。

注意，新的整數（a 或 b）必須不能 含有前導 0，并且 非 0。

思路

貪心
對于最大值a：
肯定是越高位越大越好，所以從最高位開始往后看，第一個不是9的位，這一位數全改成9。

比如 9868 —> 9969

對于最小值b：
肯定是越高位越小越好，
但是有個條件，不能為0，也不能有前置0，
所以不能直接從最高位開始看，要先看最高位是不是1，
①如果不是1，就直接把他和它相同的改成1就行了；
②如果是1，就從后看第一個不是1也不是0的改成0。（這里不能直接按不是0的都改成0來算，因為不是0也包括了1，要是1的話會把第一位的1也改成0，就有前置0了）

比如 120 —> 100，就不能把第一位的1改成0，要不然就是 020 有前置0了。
比如 110 —> 110，就不能把第二位的1改成0，要不然就是000了。

代碼

①給的是int型的，因為要挨位訪問，所以先轉成String，再轉成char[]，因為char[]訪問效率比String高。
②然后因為有 “將num中所有出現 x 的數位都用 y 替換" 這個操作，可以單獨封裝一下，用String的replace方法，這個方法不會改變原String，只會返回新String。
③a和b要初始化都等于num，這樣防止兩次都沒有操作的情況
比如 999、111、100

class Solution {public int replace(String str, char c, char toWhat){String temp = str.replace(c, toWhat);   // 不會改變原字符串return Integer.valueOf(temp);}public int maxDiff(int num) {String numStr = String.valueOf(num);char[] numChar = numStr.toCharArray();int a=num, b=num;     // 初始值num，防止999和000或者111之類的情況// 找最大for(char numC : numChar){if(numC != '9'){a = replace(numStr, numC, '9');break;}}// 找最小if(numChar[0] != '1'){b = replace(numStr, numChar[0], '1');}else{for(int i=1; i<numChar.length; i++){if(numChar[i]!='0' && numChar[i]!='1'){b = replace(numStr, numChar[i], '0');break;}}}return a-b;}
}

時間復雜度：O(logN)
空間復雜度：O(logN)