[LeetCode] 556. Next Greater Element III

_ang 发布于2019-08-16 13:47 / 2685人阅读

Problem

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

Example 3:

Input: 123987
Output: 127389

Solution

class Solution {
    public int nextGreaterElement(int n) {
        char[] num = (n+"").toCharArray();
        int i;
        for (i = num.length-1; i > 0; i--) {
            if (num[i-1] < num[i]) break;
        }
        //when all digits are in decreasing order, no greater num
        if (i == 0) return -1; 
        
        //otherwise we get the last increasing digit: num[i-1]
        //and loop to the end finding the smallest greater digit than num[i-1]
        int smallestGreaterIndex = i;
        int lastIncreasing = num[i-1];
        for (int j = i+1; j < num.length; j++) {
            if (num[j] > lastIncreasing && num[j] <= num[smallestGreaterIndex]) {
                smallestGreaterIndex = j;
            }
        }
        //123987 -> lastIncreasing = 3, smallestGreaterIndex = 5
        //swap 3 and 7 -> 127983
        char temp = num[i-1];
        num[i-1] = num[smallestGreaterIndex];
        num[smallestGreaterIndex] = temp;
        
        //reorder 983 to 389 -> 127389
        Arrays.sort(num, i, num.length);
        
        //parse to long to avoid overflow
        long val = Long.parseLong(new String(num));
        return val > Integer.MAX_VALUE ? -1 : (int) val;
    }
}

云服务器 GPU云服务器 Greater III Element LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/72322.html

Leetcode PHP题解--D52 496. Next Greater Element I

摘要：题目链接题目分析给定两个数组，其内元素不重复。数组是数组的子集，返回每个在数组中的元素在数组对应位置以右最大的元素。思路只能逐个遍历吧。最终代码若觉得本文章对你有用，欢迎用爱发电资助。 D52 496. Next Greater Element I 题目链接 496. Next Greater Element I 题目分析给定两个数组，其内元素不重复。数组1是数组2的子集，返回每个...

only_do 2019-07-01 12:44 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0
13. 罗马数字转整数-----leetcode刷题（python解题）

摘要：题目罗马数字包含以下七种字符，，，，，和。字符数值例如，罗马数字写做，即为两个并列的。通常情况下，罗马数字中小的数字在大的数字的右边。同样地，数字表示为。给定一个罗马数字，将其转换成整数。 [TOC] 题目罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。字符数值 I 1 V 5 X ...

Gu_Yan 2019-07-31 10:38 评论0 收藏0
LeetCode707：设计链表 Design Linked List

摘要：爱写设计链表的实现。单链表中的节点应该具有两个属性和。插入后，新节点将成为链表的第一个节点。将值为的节点追加到链表的最后一个元素。如果等于链表的长度，则该节点将附加到链表的末尾。如果索引有效，则删除链表中的第个节点。操作次数将在之内。爱写bug (ID:iCodeBugs) 设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是...

iliyaku 2019-08-16 18:34 评论0 收藏0
LeetCode707：设计链表 Design Linked List

摘要：爱写设计链表的实现。单链表中的节点应该具有两个属性和。插入后，新节点将成为链表的第一个节点。将值为的节点追加到链表的最后一个元素。如果等于链表的长度，则该节点将附加到链表的末尾。如果索引有效，则删除链表中的第个节点。操作次数将在之内。爱写bug (ID:iCodeBugs) 设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是...

FullStackDeveloper 2019-07-31 11:28 评论0 收藏0