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

题目描述

556. 下一个更大元素 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]后对应交换.

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