最大交换[贪心思想＆单调栈实现]

前言

贪心/DP是练习/考察逻辑思维的好题目，一半步骤为先纸上模拟模拟找找规律，再寻找适合的数据结构，再用代码把自己的想法实现出来。

一、最大交换

二、贪心&单调栈

/* target：最多交换一次让数值最大。 很明显，如果数值从高到低位不成单调递减状态时，就把尽可能后面最大的值交换到尽可能的前。 贪心1：把后面大的和前面小的交换； 贪心2：尽可能，对于前面，要尽可能的往前找小的，相等时也需取左；对于后面，尽可能的往后找大的，当想等时也需取右侧。 总结：贪心思想，单调栈实现。 */
    public int maximumSwap(int num) {
    
        char[] arr = String.valueOf(num).toCharArray();
        // step1:确定非单调处，以便开始往后寻最大值。
        int i = 1;
        while (i < arr.length && arr[i] <= arr[i - 1]) ++i;

        if (i == arr.length) return num;
        // step2:寻最大值所在处。
        int idx = i;
        while (i < arr.length) {
    
            if (arr[idx] <= arr[i]) idx = i;

            ++i;
        }
        // step3:寻找尽可能前的位置。
        i = 0;
        while (i < arr.length && arr[i] >= arr[idx]) ++i;
        // step4:交换位置。
        swap(arr, i, idx);

        return Integer.parseInt(String.valueOf(arr));
    }

    private void swap(char[] arr, int i, int j) {
    
        char c = arr[i];
        arr[i] = arr[j];
        arr[j] = c;
    }

总结

1）多多练习贪心/动态规划题目，对逻辑分析能力的提升有帮助。
2）面对问题，找找规律，根据数据结构特性选合适的数据结构，再用配合代码的分支/循环来解决问题，往往需要将问题转换，往数据结构&分支/循环/递归上靠。

参考文献

[1] LeetCode 最大交换