Maximum exchange [greedy thought & monotonic stack implementation]

Preface

greedy /DP It's practice / A good topic to examine logical thinking , The half step is to simulate and find the law on paper , Then find a suitable data structure , Then use code to realize your idea .

One 、 Maximum exchange

Two 、 greedy & Monotonic stack

/* target： Exchange at most once to maximize the value .  Obviously , If the value does not monotonically decrease from high to low , Just swap the largest possible value from the back to the front .  greedy 1： Exchange the big one in the back with the small one in the front ;  greedy 2： As far as possible , For the front , Try to find the small one as far forward as possible , When equal, it is also necessary to take the left ; For the back , Try to find a big one later , When you want to wait, you also need to take the right .  summary ： Greedy thoughts , Monotonic stack implementation . */
    public int maximumSwap(int num) {
    
        char[] arr = String.valueOf(num).toCharArray();
        // step1: Determine non single mediation , In order to start looking for the maximum value later .
        int i = 1;
        while (i < arr.length && arr[i] <= arr[i - 1]) ++i;

        if (i == arr.length) return num;
        // step2: Find the maximum value .
        int idx = i;
        while (i < arr.length) {
    
            if (arr[idx] <= arr[i]) idx = i;

            ++i;
        }
        // step3: Find the front position as far as possible .
        i = 0;
        while (i < arr.length && arr[i] >= arr[idx]) ++i;
        // step4: Swap places .
        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;
    }

summary

1） Practice greed more / Dynamic planning topic , It is helpful to improve the ability of logical analysis .
2） Facing problems , Find the law , Select the appropriate data structure according to the characteristics of the data structure , Then use the branch of the matching code / Cycle to solve the problem , It is often necessary to transform the problem , Go to data structure & Branch / loop / Recursive up .

reference

[1] LeetCode Maximum exchange