leetcode556. Next Greater Element III

本文主要是介绍leetcode556. Next Greater Element III，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目要求

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:

Input: 12
Output: 21

Example 2:

Input: 21
Output: -1

现有一个32位的正整数，要求找到用该正整数中同样的数字组成的比该正整数大的最小正整数。
比如现有正整数245，比该正整数大的数字包括425,452,254,542,524, 该方法应当返回254

思路和代码

有一个基本的思路我们知道，如果要找到大于当前数字的最小正整数，我们应当尽可能的保证高位不发生变化，通过交换低位的数字得到相对而言更大的正整数。

因此从右往左遍历，一旦找到一个数字，其值低于已经遍历过的任何一个值，则可以将从该值起右侧的所有数字的顺序进行调整，找到一个大于该子整数的最小正整数。

举个例子：53421，从右往左遍历可以3小于其右侧的任何一个值，则将3和右侧最小的整数进行交换得到51423，再对1右侧的所有数字按照从小到大进行排序，则可以得出大于53421的最小正整数，即51234

代码如下：

public int nextGreaterElement(int n) {  
    String value = String.valueOf(n);  
    char[] digits = value.toCharArray();  
    int i = digits.length - 1;  
    //找到小于右侧任意值的第一个正整数
    while (i > 0) {  
        if (digits[i - 1] < digits[i]) {  
            break;  
        }  
        i--;  
    }  
    
    if (i == 0) {  
        return -1;  
    }  
  
    //找到该整数右侧大于该整数的最小整数
    int maxIndex = i, j = i;  
    while (j < digits.length) {  
        if (digits[j] <= digits[maxIndex] && digits[j] > digits[i-1]) {  
            maxIndex = j;  
        }  
        j++;  
    }  
  
    //交换两个整数
    char tmp = digits[i-1];  
    digits[i-1] = digits[maxIndex];  
    digits[maxIndex] = tmp;  
  
    //对整数右侧的值按照从小到大进行排序
    Arrays.sort(digits, i, digits.length);  
  
    long result = Long.valueOf(String.valueOf(digits));  
    return result < Integer.MAX_VALUE ? (int) result : -1;  
}

这篇关于leetcode556. Next Greater Element III的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！