day-16 最大交换

思路
用一个数组存储各数位上的数字，然后从最高位开始依次检查是否存在低位数位上的数大于自己，有则交换

解题方法
用一个数组存储各数位上的数字
求出num的位数
注意：当数位上的数字相等时，可能交换，也可能不交换，注意分类讨论

时间复杂度,： O(n2)
空间复杂度,： O(n)

Code

class Solution {
    public static int maximumSwap(int num) {
        int arr[]=new int[8];
        int i=0;
        while(num!=0){
            arr[i]=num%10;
            num=num/10;
            i++;
        }
        i=7;
        while(arr[i]==0){
            i--;
        }
        int len=i+1;
        int j,max;
        for(i=len-1;i>0;i--){
            boolean flag=true;
            max=arr[i];
            int po=i;
            for( j=i-1;j>=0;j--){
                if(arr[j]>max||(arr[j]==max&&flag==false)){
                    po=j;
                    max=arr[po];
                    flag=false;
                }
            }
            if(flag==false){
                int t=arr[i];
                arr[i]=arr[po];
                arr[po]=t;
                break;
            }
        }
        int ans=0;
        for(i=len-1;i>=0;i--){
            ans=ans+f(i)*arr[i];
        }
        return ans;
    }

    static int f(int num){
        int ans=1;
        for(int i=0;i<num;i++){
            ans=ans*10;
        }
        return ans;
    }
}