670. 最大交换(中等)

Posted on In Views:

1，问题描述

670. 最大交换

难度：中等

给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。

示例 1 :

1
2
3
输入: 2736
输出: 7236
解释: 交换数字2和数字7。

示例 2 :

1
2
3
输入: 9973
输出: 9973
解释: 不需要交换。

注意:

  1. 给定数字的范围是 [0, 108]

2，初步思考

​ 我自己首先想到的是单调栈来解决这个问题，这个有点像最大有效扣号数目的题目

​ 其他人的题解中有一个很厉害的观点，就是直接去模拟

3，代码处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
import support.Pair;

import java.util.ArrayDeque;
import java.util.Deque;

public class _670最大交换 {

    public int maximumSwap_gov(int num) {
        char[] array = String.valueOf(num).toCharArray();
        int maxIndex = array.length - 1, swapIndex = -1, minIndex = -1, len = array.length;
        for (int i = len - 1; i >= 0; i--) {
            if (array[i] > array[maxIndex]) {// 更新最大数idx
                maxIndex = i;
            } else if (array[i] < array[maxIndex]) {// 更新交换位置的点
                swapIndex = maxIndex;// 大值
                minIndex = i;// 小值
            }
        }
        if (minIndex == -1) {
            return num;
        }// 如果没有找到，则返回原值
        char tmp = array[swapIndex];
        array[swapIndex] = array[minIndex];
        array[minIndex] = tmp;
        return Integer.parseInt(String.valueOf(array));
    }

    public void swap(char[] charArray, int i, int j) {
        char temp = charArray[i];
        charArray[i] = charArray[j];
        charArray[j] = temp;
    }


    // 优化版
    public int maximumSwap_fail(int num) {
        char[] charArray = String.valueOf(num).toCharArray();
        int left = 0, right = charArray.length - 1;
        while (left < charArray.length - 1) {// 找到第一个比后面大的数，这个一定是要被替换的数值
            if (charArray[left] < charArray[left + 1]) {
                break;
            }
            left++;
        }
        if (left == charArray.length) return num;// 数组为单调降序排列，以及是最大值

        // 找到最大的数据
        int idx = right;
        int max = charArray[idx];
        while (right > left) {
            if (charArray[right] > max) {
                max = charArray[idx];
                idx = right;
            }
            right--;
        }

        // 替换位置
        char temp = charArray[left];
        charArray[left] = charArray[idx];
        charArray[idx] = temp;
        return Integer.parseInt(new String(charArray));
    }

    public int maximumSwap(int num) {
        char[] charArray = String.valueOf(num).toCharArray();
        Deque<Pair<Character, Integer>> maxStack = new ArrayDeque<>();
        for (int i = charArray.length - 1; i >= 0; i--) {
            if (maxStack.isEmpty() || maxStack.peek().getKey() < charArray[i]) {
                maxStack.push(new Pair<>(charArray[i], i));
            }
        }

        for (int i = 0; i < charArray.length && !maxStack.isEmpty(); i++) {
            if (charArray[i] == maxStack.peek().getKey() && maxStack.peek().getValue() <= i) {
                maxStack.pop();
                continue;
            }
            if (charArray[i] < maxStack.peek().getKey()) {
                Pair<Character, Integer> peek = maxStack.peek();
                char temp = charArray[i];
                charArray[i] = peek.getKey();
                charArray[peek.getValue()] = temp;
                break;
            }
        }
        return Integer.parseInt(new String(charArray));
    }

    public static void main(String[] args) {
        _670最大交换 maximumSwap = new _670最大交换();
        System.out.println(maximumSwap.maximumSwap_optimize(999879));
        System.out.println(maximumSwap.maximumSwap_optimize(9973));
        System.out.println(maximumSwap.maximumSwap_optimize(1993));
        System.out.println(maximumSwap.maximumSwap_optimize(98368));
    }
}
/**
 * 999879
 * 654321234
 */