Star

LeetCode Weekly Contest 27: 556. Next Greater Element III

Posted on | In |

Question

Given a positive 32-bit integer n, you need to find the smallest 32-bit integer which has exactly the same digits existing in the integer n and is greater in value than n. If no such positive 32-bit integer exists, you need to return -1.

Example 1: 

1
2
Input: 12
Output: 21

Example 2: 

1
2
Input: 21
Output: -1

Explanation

思路是：从最后开始，每两个数对比，如果前一个数比后一个数小，停下，这点就是要变的地方。然后，把这个位置用后面比它大的数中最小的那个数字替代，互换位置。之后再把这个位置后面的所有数倒置一下。同LeetCode No.31

比如 12487653
先替换 12587643
再倒置后面的数字 12534678

Code

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
public int nextGreaterElement(int num) {
        String n = Integer.toString(num);
        char[] nums = n.toCharArray();
        if (nums.length<=1) return -1;
        int result = -1;
        for (int i=nums.length-2;i>=0;i--) {
            if (nums[i] >= nums[i+1]) continue;
            swap(nums,i);
            reverse(nums, i+1);
            //avoid overflow
            try {
                return Integer.parseInt(new String(nums));
            } catch(Exception e) {
                return -1;
            }
        }
       return result;
}
public void swap(char[] nums, int i) {
    for (int j =nums.length-1; j>i; j--) {
        if (nums[j] > nums[i]){
            char c = nums[j];
            nums[j] = nums[i];
            nums[i] = c;
            break;
        }
    }
}
public void reverse(char[] nums,int i) {
    int first = i;
    int last = nums.length-1;
    while(first < last) {
        char c = nums[first];
        nums[first] = nums[last];
        nums[last] = c;
        first ++;
        last --;
    }
}