LeetCode Next Greater Element III Given a positive 32-bit integer n, you need to find the smallest 32-bit integer which has exactly the same digits existing in the integer n and is greater in value than n. If no such positive 32-bit integer exists, you need to return -1. Example 1:
Input: 12 Output: 21Example 2:
Input: 21 Output: -1
给定一个数n，要求用和n一样的数字，重组成一个比n大的最小的数。如果不存在这样的数，输出-1。 比如样例1，n=12，则同样用数字1和2，重组出比12大的最小的数就是21。如果n本身等于21，则无法用数字1和2重组出比21更大的数了。 首先很容易想到无解的情况，比如n=76543210，因为n的数字从左到右是非升序的，所以n本身已经是最大的了，无法重组出比n更大的数。所以隐隐约约感觉可以从左往右找第一个上升的位置。 再来，n=76546743，如果从左往右找第一个上升的位置，则是i=3的数字4，4->6是上升的，所以可以考虑从4后面找比4大的最小的数，也就是6，交换4和6，变成76564743，因为原来为4的位置已经变成更大的6了，所以6后面最小即可，对6后面的数排序，变成了76563447。 但是76563447并不是比n大的最小的数，另外还有76547346，也就是不变4，而是变i=4的数字6。所以换一种思路，我们从右往左找第一个下降的位置，比如这里是i=5的数字7，然后从该位置往右找一个比i-1的数6大的最小的数7，交换他们的位置，同时把i-1右边的数从小到大排序。 再比如n=12443322，从右往左找第一个下降的位置是i=2，数字为4，从该位置找一个比i-1的数2大的最小的数是i=4的数3，交换他们n=1344222，再对i-1右边的数从小到大排序，得到n=1322244。 完整代码如下，另外需要注意结果不能超出int范围，所以先转换为long long，再和INT_MAX比较。 [cpp] class Solution { public: int nextGreaterElement(int n) { string s = to_string(n); int m = s.size(); for (int i = m – 1; i > 0; –i) { if (s[i] > s[i – 1]) { int pos = i; for (int j = i; j < m; ++j) { if (s[j] > s[i – 1] && s[j] < s[pos]) { pos = j; } } swap(s[pos], s[i – 1]); sort(s.begin() + i, s.end()); long long ans = stoll(s); if (ans <= INT_MAX)return ans; else return -1; } } return -1; } }; [/cpp] 本代码提交AC，用时3MS。]]>