Leetcode 556. Next Greater Element III

用户头像
隔壁小王
关注
发布于: 2020 年 05 月 16 日
Leetcode 556. Next Greater Element III

Description

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

Input: 12
Output: 21



Input: 21
Output: -1



问题分析

  1. 求解目标:找到第一个大于 n、且满足条件的数字(条件:数字组成不变)。

  2. 一个规律:给定一串数字,如 2135,其可能发生的由小变大的变化,必然是个位先更新,其次是十位,以此类推。

  3. 边界条件:给定一串数字,如 2135,数字的变化何时能够达到最大值?必然是这串数字从个位到最高位是升序时,也即 5321。



求解步骤

  1. 给定输入 n = 2135,从个位(最后一位)开始向前遍历,直到找到第一个降序的数字为止,即 3;

  2. 此时问题的规模被缩小为 n = 35,而无须关心更高位的数字(见问题分析2);

  3. 子问题求解:除最高位数字外,其他位数字为升序时,如何寻找满足条件的数?

比如 n 为 35、153、16532、15321等。

  • 首先,确定新的最高位。由于除最高位之外的数字是升序的,因此下一步必然是更新最高位。在除最高位的数字中找到第一个大于最高位的数字,将其作为新的最高位。

  • 其次,将剩余的所有数字,按照从小到大的顺序排列,以使得除最高位之外,其余数字组成的值最小



其他

  1. 注意题目中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 日 阅读数: 26
用户头像

隔壁小王

关注

还未添加个人签名 2020.04.29 加入

还未添加个人简介

评论

发布
暂无评论
Leetcode 556. Next Greater Element III