179.最大数

两层遍历, 形似插入排序, 每次找到能最大化添加的数字append到ans里面

class Solution {
    /**
     * 两层遍历, 形似插入排序, 每次找到能最大化添加的数字append到ans里面
     */
    public String largestNumber(int[] nums) {
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < nums.length; i++) {
            // 每次选一个数字添加
            int next = -1; // 下一个要添加的数字的索引
            for (int j = 0; j < nums.length; j++) {
                int x = nums[j];
                if (x == -1) continue;
                if (next == -1) {
                    next = j;
                    continue;
                }
                int max = nums[next];
                if (!moreThan(max, x)) {
                    next = j;
                }
            }
            ans.append(nums[next]);
            nums[next] = -1;
        }
        String ret = ans.toString();
        return ret.charAt(0) != '0'
                ? ret
                : "0";
    }

    // 如果max x大于x max返回true, 否则返回false
    private boolean moreThan(int max, int x) {
        int d1 = numDigit(max);
        int d2 = numDigit(x);
        if (d1 == d2) {
            return max >= x;
        }
        long num1 = max * (int) Math.pow(10, d2) + x;
        long num2 = x * (int) Math.pow(10, d1) + max;
        return num1 >= num2;
    }

    private int numDigit(int num) {
        int ans = 1;
        while ((num /= 10) > 0) {
            ans++;
        }
        return ans;
    }
}