一、题目描述：
继续刷下一个更大元素 III ，看看本次需要用什么方式来进行处理 ，会不会还是单调栈？
二、这道题考察了什么思想？你的思路是什么？
仔细看题目，貌似本次没有明着或者暗着的让我们找下一个更大的元素了，而是有其他的要求
- 题目给出一个整数 n，让我们将这个整数中的每一个数字进行一个排列，需要我们找到一个最小的大于 n 的整数
- 且有一个要求，这个结果整数不能大于 32 位的最大范围，即 2^32 -1
分析
仔细看这个题，会不会第一想法还是想到的是单调栈的方式来进行处理？会不会有一种惯性思维，实际上这次用不上单调栈了，因为这一次很明显是要咱们找全排列了
对于一串数据的全排列，当然最简单的方式可能是将这串数据的所有全排列全部找出来，然后去判断哪一个才是大于 n 的最小整数
例如， n 为 123，那么全排列就有 6 种
| 1 | 2 | 3 |
| 1 | 3 | 2 |
| 2 | 1 | 3 |
| 2 | 3 | 1 |
| 3 | 1 | 2 |
| 3 | 2 | 1 |
那么，咱们进行比较和判断，就能找到大于 123 的最小整数是 132
这样处理也不是不可以，但是有点挫，咱们可以完全没有必要去找那些我们不关心的全排列咱们只需要找到正好比 n 大的全排列就可以了，即 下一个全排列
那么如何找到下一个全排列呢？
举个例子
n = 123796
- 咱们可以先从后先前找某一个元素正好是第一个比后面的一个元素小，例如找到 7，（此时索引为 3 ，此时说明 索引 3 后面的数字一定是比后一位要大的，因此后续需要做翻转，才是最小的）
- 再从后往前找，某一个元素正好是第一个比 7 大的数，也就是 9
- 交换 7 和 9 的位置， 123976
- 这个时候，再去翻转索引 3 后面的内容，则为 123967 ，因此结果为 123967
看到这里，实际上咱们主要是知道如何去找下一个全排列的方法，没有什么弯弯绕绕，主要是需要我们知道这个方式
接下来就来实现手撸代码吧
三、编码
根据上述逻辑和分析，我们就可以翻译成如下代码
- 将 n 转换成 byte 数组，再对其查找他的下一个全排列
- 先 找到第一个比自己后面一个元素小的元素 索引 i ，找到之后，说明 i 后面的元素都是逐个比后面大的（因此后续需要进行翻转，才可以是正好比 n 大的最小整数）
- 再找到第一个比 i 索引大的元素索引 j
- 交换 i 和 j 对应的值
- i 后面的元素进行翻转，例如 i 后面是 321，翻转之后就是 123
- 判断结果是否符合要求，这个结果整数不能大于 32 位的最大范围，即 2^32 -1
编码如下：
func nextGreaterElement(n int) int { // 将数字转换成 byte 数组 // 再对其查找他的下一个全排列 nums := []byte(strconv.Itoa(n)) // 找到第一个比自己后面一个元素小的元素 索引 i ，找到之后，说明 i 后面的元素都是逐个比后面大的 i := len(nums) -2 for i >=0 && nums[i] >= nums[i+1] { i-- } if i < 0 { return -1 } // 再找到第一个比 i 索引大的元素索引 j j := len(nums) -1 // 此处退出循环后， j 不可能小于 0 for j>=0 && nums[i] >= nums[j] { j-- } // 交换 i 和 j 对应的值 nums[i], nums[j] = nums[j], nums[i] // i 后面的元素进行翻转，例如 i 后面是 321，翻转之后就是 123 myReverse(nums[i+1:]) // 判断结果是否符合要求 res,_ := strconv.Atoi(string(nums)) if res > math.MaxInt32 { return -1 } return res } func myReverse(nums []byte){ n := len(nums) for i:=0; i<n/2; i++ { nums[i], nums[n-1-i] = nums[n-1-i], nums[i] } }
四、总结：
本题咱们的这种处理方式，实际上就是找一个序列的下一个全排列，时间复杂度是 O(logn)，空间复杂度也是 O(logn)
原题地址：556. 下一个更大元素 III
欢迎点赞，关注，收藏
朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力
好了，本次就到这里
技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。
我是阿兵云原生，欢迎点赞关注收藏，下次见~
