下一个更大元素III

发表于 分类于

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/next-greater-element-iii

题目

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

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

思路

题目是出门时看的，当时看到就觉得应该是写过很多次的全排列。但我依稀记得之前写的全排列不是超时就是WA，回来的时候仔细看了题目，原来只是求下一个，而不是全部的。

然后对着用例研究了半天，再自己构造些用例，确定了方法：

先从低位往高位找，找到第一个当前位＞高一位的数字。再从低位找一个比这个高一位数字大的最小值，这个时候将这两个数字交换，高位部分就是已经确定的了。

1
2
3
4
5
6
7
114514
1 > 4
11454 | 1

114514321
1 > 4
11452 | 4311

然后低位按升序排列，确保小的数再前，构造出一个最小的数

1
11454 | 1321 =》 11452 | 1134

然后再把这个数转换为Long，判断是否超过Integer.MAX_VALUE即不是32位整数。

总结

一遍过了，看了眼官方题解。思路是一致的，但是人家写的更简洁高效，最后低位只会是降序的一排列，所以只需要反转转为升序，不需要排序。

看了一眼评论区，C++的stl有next_permutation可以直接求下一个排列，然后清一色的《回去等通知》。

我个人感觉用这东西其实挺好的，虽然写算法题的本质不是让你调库，但是在日常写代码中，如果我知道有这一个函数，我是不会重新写一遍算法的。我觉得算法重要的一点是思路，这也是我为什么不贴代码的原因。以后遇到相关的问题，回来看自己的博客，看半天代码去试图理解曾经的自己写的是什么太困难了，而看思路则会更想打死曾经的自己在写什么清晰很多。

但是光有思路还不够，还需要较强的代码功底，Java写多了，满脑子都是面向对象，写的都是封装、继承和各种设计模式，这也是为什么写的代码不如题解简洁高效。