# # 【LeetCode】556. Next Greater Element III 解题报告（Python）

## # 题目描述：

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

## # 解题方法

31. Next Permutationopen in new window解题方式基本一模一样，先找到从后向前数，第一个降序的位置，把此位置后面的翻转。再把这个降序数字和后面第一个比它大的位置交换即可。

class Solution(object):
def nextGreaterElement(self, n):
"""
:type n: int
:rtype: int
"""
nums = list(str(n))
n = len(nums)
i = n - 1
while i > 0 and nums[i] <= nums[i - 1]:
i -= 1
if i == 0:
return -1
self.reverse(nums, i, n - 1)
for j in range(i, n):
if nums[j] > nums[i-1]:
self.swap(nums, i-1, j)
break
ans = int("".join(nums))
if ans > 1 << 31:
return -1
else:
return ans

def reverse(self, nums, i, j):
"""
contains i and j.
"""
for k in range(i, (i + j) / 2 + 1):
self.swap(nums, k, i + j - k)

def swap(self, nums, i, j):
"""
contains i and j.
"""
nums[i], nums[j] = nums[j], nums[i]

1. https://leetcode.com/articles/next-permutation/
2. https://blog.csdn.net/tstsugeg/article/details/50261517

## # 日期

2018 年 8 月 27 日 ———— 就要开学了！