LeetCode Next Greater Element III

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: 21

Example 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比较。

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;
	}
};

本代码提交AC,用时3MS。

Leave a Reply

Your email address will not be published. Required fields are marked *