题解 | #最大数字交换#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num string字符串 
     * @return string字符串
     */
    
    /**********************************************************************************/
    // 暴力破解法
    /*
    public String maximumSwap (String num) {
        // write code here
        if (1 == num.length()) {
            return num;
        }
        char[] chrs = num.toCharArray();
        char[] resChar = num.toCharArray();
        for (int i = 0; i < num.length(); i++) {
            char chr1 = chrs[i];
            for (int j = i + 1; j < num.length(); j++) {
                char chr2 = chrs[j];
                if (chr1 < chr2) {
                    chrs[i] = chr2;
                    chrs[j] = chr1;
                    if (process(chrs, resChar)) {
                        resChar = Arrays.copyOf(chrs, chrs.length);
                    }
                    chrs[i] = chr1;
                    chrs[j] = chr2;
                }
            }
        }
        StringBuffer sb = new StringBuffer("");
        for (char chr : resChar) {
            sb.append(chr);
        }
        return new String(sb);
    }
    
    public boolean process(char[] chrs1, char[] chrs2) {
        for (int i = 0; i < chrs1.length; i++) {
            if (chrs1[i] > chrs2[i]) {
                return true;
            }
            else if (chrs1[i] < chrs2[i]) {
                return false;
            }
        }
        return false;
    }
    */
    
    /**********************************************************************************/
    // 贪心算法
    public String maximumSwap (String num) {
        if (1 == num.length()) {
            return num;
        }
        char[] chrs = num.toCharArray();
        char chr = chrs[0];
        LinkedList<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < chrs.length; i++) {
            if (chrs[i] >= chr) {
                linkedList.add(i);
                chr = chrs[i];
            }
        }
        if (linkedList.isEmpty()) {
            return num;
        }
        int index = linkedList.peekLast();
        for (int i = 0; i < index; i++) {
            chr = chrs[i];
            if (chr < chrs[index]) {
                chrs[i] = chrs[index];
                chrs[index] = chr;
                break;
            }
        }
        StringBuffer sb = new StringBuffer("");
        for (char ch : chrs) {
            sb.append(ch);
        }
        return new String(sb);
    }
}