# \[556]\[中等]\[栈] 下一个更大元素 III

## 题目描述

[556. 下一个更大元素 III](https://leetcode-cn.com/problems/next-greater-element-iii/)

给你一个正整数 n ，请你找出符合条件的最小整数，其由重新排列 n 中存在的每位数字组成，并且其值大于 n 。如果不存在这样的正整数，则返回 -1 。

注意 ，返回的整数应当是一个 32 位整数 ，如果存在满足题意的答案，但不是 32 位整数 ，同样返回 -1 。

示例 1：

```
输入：n = 12
输出：21
```

示例 2：

```
输入：n = 21
输出：-1
```

提示：

* 1 <= n <= 2^31 - 1

## 解题思路

如果一个序列从高位到低位是降序的, 这不会有更大的排列可能出现. 因此对于一个数字, 我们从后向前找, 找到第一个打破升序的元素, 这个元素可以与后面的某个更大的元素交换, 得到新的更大值.

新的更大值, 在第一个打破升序元素的位置(记为a\[i])上, 需要比之前的这个数字更大, 而且这个数字来自于它之后的数字序列, 且这个数字不能过大, 应当是大于a\[i]的序列中的最小值.

我们在从后向前遍历的过程中, 会将一个升序序列逐个压入栈中, 得到的栈是一个**单调递增栈**, 栈顶元素最大. 因此在确定了a\[i]之后, 就要比较这个栈的栈顶于a\[i]的大小, 将大于a\[i]的元素pop, 直到遇到第一个不大于a\[i]的元素, 或者栈空了, 此时我们pop出去的最后一个元素, 就是大于a\[i]的最小元素, 记为a\[j], 交换i和j对应数字的位置.

交换数字后, i位置之后的序列仍然是一个递减子序列, 现在i位变大了, 为了得到最近的一个更大值, i之后的序列排列应该变为最小, 就是一个递增子序列, 所以将交换后的递减子序列逆转就好了.

另外, 单调栈中记录的元素应当是每个元素的索引, 方便在找到a\[j]后对应交换.

```python
class Solution:
    def nextGreaterElement(self, n: int) -> int:
        digits = list(str(n))
        stack = []
        swap_index = -1
        for i in range(len(digits) - 1, -1, -1):
            # 发现当前值比栈顶元素小, pop栈顶元素直到栈顶不大于当前元素, 记录最后一个大于栈顶的元素位置
            while stack and digits[i] < digits[stack[-1]]:
                swap_index = stack.pop()

            # 交换当前元素与之前大于它的最小值, 然后将后半部分逆序
            if swap_index >= 0:
                digits[i], digits[swap_index] = digits[swap_index], digits[i]
                digits = digits[:i + 1] + digits[i + 1:][::-1]
                num = int(''.join(digits))
                return num if num < 1 << 32 - 1 else -1

            # 单调递增栈, 记录索引
            stack.append(i)
        return -1
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kerasnoone.gitbook.io/garnet/suan-fa/zhan/503-xia-yi-ge-geng-da-yuan-su-iii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.