# 556. Next Greater Element III

{% embed url="<https://leetcode.com/problems/next-greater-element-iii/>" %}

跟前天的这道题基本一模一样，ctrl+c/v...

{% content-ref url="combination-and-permutation/31.-next-permutation" %}
[31.-next-permutation](https://xuqiangwen1994.gitbook.io/practice/combination-and-permutation/31.-next-permutation)
{% endcontent-ref %}

smallest great --> 基本思路是找到能改大的最小digit

1. 因为是最小digit，从右往左找
2. 用的数字不能变，所以「改大」就是能和自己右侧较大数字交换位置

```python
class Solution:
    def nextGreaterElement(self, n: int) -> int:
        nums = [str(n)[x] for x in range(len(str(n)))]
        i = len(nums)-1
        while i > 0:
            if nums[i-1] >= nums[i]:
                i -= 1
            else:
                pivot = i
                while pivot < len(nums)-1:
                    if nums[pivot+1] <= nums[i-1]: break
                    pivot += 1
                nums[i-1], nums[pivot] = nums[pivot], nums[i-1]
                nums[i:] = nums[i:][::-1] # 倒转list切片，这个值得记忆一下...
                break
        
        res = int(''.join(nums))
        
        if i == 0 or res>2**31-1:
            return -1

        return res
```
