专栏首页眯眯眼猫头鹰的小树杈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;  
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode423. Reconstruct Original Digits from English

    一个非空的英文字符串,其中包含着乱序的阿拉伯数字的英文单词。如012对应的英文表达为zeroonetwo并继续乱序成owoztneoer。要求输入乱序的英文表达...

    眯眯眼的猫头鹰
  • leetcode389.Find The Difference

    假设两个只包含小写字母的字符串s和t,其中t是s中字母的乱序,并在某个位置上添加了一个新的字母。问添加的这个新的字母是什么?

    眯眯眼的猫头鹰
  • leetcode341. Flatten Nested List Iterator

    首先可以想到通过深度优先递归的方式将嵌套形式的数组展开为一个无嵌套的列表。那么有没有方法实现不将元素取出而是直接迭代的方式获取下一个元素呢?这里采用了嵌套迭代器...

    眯眯眼的猫头鹰
  • 【LeetCode】66. Plus One

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • [Leetcode][python]Plus One/加一

    后端技术漫谈
  • Swift 加一 - LeetCode

    语文能力捉急啊,看了半天没看懂。。。然后去找了英文原题(我实在LeetCode中文网做的题),英文描述如下:

    韦弦zhy
  • Python实现"加一"的两种方法

    算法题来自:https://leetcode-cn.com/problems/plus-one/description/

    py3study
  • LeetCode 66. 加一

    freesan44
  • 66. 加一

    Michel_Rolle
  • leetcode-17-电话号码的字母组合

    vector<string> letterCombinations(string digits) 

    chenjx85

扫码关注云+社区

领取腾讯云代金券