Leetcode 556. Next Greater Element III

关注

发布于: 2020 年 05 月 16 日

DescriptionGiven 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
Input: 12
Output: 21
﻿
Input: 21
Output: -1
﻿
问题分析求解目标：找到第一个大于 n、且满足条件的数字（条件：数字组成不变）。
一个规律：给定一串数字，如 2135，其可能发生的由小变大的变化，必然是个位先更新，其次是十位，以此类推。
边界条件：给定一串数字，如 2135，数字的变化何时能够达到最大值？必然是这串数字从个位到最高位是升序时，也即 5321。
﻿
求解步骤给定输入 n = 2135，从个位（最后一位）开始向前遍历，直到找到第一个降序的数字为止，即 3；
此时问题的规模被缩小为 n = 35，而无须关心更高位的数字（见问题分析2）；
子问题求解：除最高位数字外，其他位数字为升序时，如何寻找满足条件的数？
比如 n 为 35、153、16532、15321等。
首先，确定新的最高位。由于除最高位之外的数字是升序的，因此下一步必然是更新最高位。在除最高位的数字中找到第一个大于最高位的数字，将其作为新的最高位。
其次，将剩余的所有数字，按照从小到大的顺序排列，以使得除最高位之外，其余数字组成的值最小。
﻿
其他注意题目中32位整数的限制，最大值为 2^31-1.
Submission
class Solution:
    def getNumber(self, array: list) -> int:
        res = 0
        for c in array:
            res = res * 10 + ord(c) - ord('0')
        return res
    
    def intoSmallestNumber(self, array: list) -> int:
        array.sort()
        res = self.getNumber(array)
        return res
    
    def nextGreaterElement(self, n: int) -> int:
        array = list(str(n))
        
        # step1: find index, array[index] < array[index+1] 
        index = len(array) - 2
        while(index >= 0):
            if(array[index] < array[index+1]):
                break
            index -= 1
        if(index == -1):
            return -1
        
        # step2: find new highest bit from array[index+1:]
        newHighestBit = len(array) - 1
        while(newHighestBit > index):
            if(array[newHighestBit] > array[index]):
                break
            newHighestBit -= 1
        
        # step3: exchange array[index] and array[newHighestBit]
        tmp = array[index]
        array[index] = array[newHighestBit]
        array[newHighestBit] = tmp
        
        # step4: calculate result by array[0:index+1] and array[index+1:]
        bits = len(array[index+1:])
        res = self.getNumber(array[0:index+1]) * 10**bits + self.intoSmallestNumber(array[index+1:])
        if(res > 2**31 - 1):
            return -1
        return res
﻿

发布于: 2020 年 05 月 16 日阅读数: 46

原文链接:【http://xie.infoq.cn/article/7ac1d5c835531df01f3d0dfb4】。文章转载请联系作者。

隔壁小王

关注

还未添加个人签名 2020.04.29 加入

还未添加个人简介

发布

暂无评论

创作场景

Leetcode 556. Next Greater Element III

Description

Example

问题分析

求解步骤

其他

Submission

隔壁小王

评论