Maximum Swap

LeetCode Q 670 - Maximum Swap

Given a non-negative integer, you could swap two digits at most once to get the maximum valued number. Return the maximum valued number you could get.

Example 1:
Input: 2736 ; Output: 7236
Explanation: Swap the number 2 and the number 7.

Example 2:
Input: 9973 ; Output: 9973
Explanation: No swap.

Note: The given number is in the range [0, 108].

Solution

Solution 1: Greedy

The left and right digits we swap should satisfy the following property, if we want to get the maximum num after the exchange.

1. the index of left digit should be as small as possible.
2. the index of right digit should be as large as possible. And the right digit should be larger than the left digit.

In the following code, we use an array, i.e. int[] last to records the largest index of 0, 1, 2, .., 9 of the given num.

Code:

public int maximumSwap(int num) {
	char[] chs = (num + "").toCharArray();
	int[] last = new int[10];

	for (int i = 0; i < chs.length; i++) {
		last[chs[i] - '0'] = i;
	}

	for (int i = 0; i < chs.length; i++) {
		for (int j = 9; j > chs[i] - '0'; j--) {
			if (last[j] > i) {
				int temp = chs[i];
				chs[i] = chs[last[j]];
				chs[last[j]] = temp;
				return Integer.parseInt(String.valueOf(chs));
			}
		}
	}

	return num;
}

Solution 2: Stack

Code:

public int maximumSwap(int num) {
	char[] chs = (num + "").toCharArray();
	
	Stack<Integer> stack = new Stack<>();
	stack.push(chs[0]);
	
	int res = num;

	for (int i = 1; i < chs.length; i++) {
		int left = -1;
		while (!stack.isEmpty() && chs[i] > chs[stack.peek()]) {
			left = stack.pop;
		}

		if (left == -1) {
			stack.push(i);

		} else {
			res = Math.max(res, swapAndTransform(num, i, left));
			stack.push(left);
		}
	}

	return res;
}

private static int swapAndTransform(int num, int i, int j ){
	char[] chs = (num+"").toCharArray();
	char temp = chs[i];
	chs[i] = chs[j];
	chs[j] =temp;
	return Integer.parseInt(new String(chs));
}