[LeetCode] 556. Next Greater Element III

轉自LeetCode

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 nand 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

<Solution>

Next Greater Element 的衍生題，但和前面兩題比較沒有關係

反而是和 31. Next Permutation 比較相近

這題簡單來說，其實就是找出下一個排列組合

例如 123，按照順序大小的下一個排列組合就是 132

想法如下

• 從數字尾端開始往前找，找到第一個降冪數字的位置；如果沒找到，就直接回傳 -1。例如1237985，紀錄 7 的位置

• 在排序的數字中，找到第一個比 7 大的數字，然後 swap。1238975

• 然後將 8 之後的數字，前後兩兩做swap。1238579。或是對 8 之後的數字做 sorting 也可以

• 檢查是不是大於 INT_MAX，是的話回傳 -1，不是的話就是答案

code如下

C++

	class Solution {
	public:
	int nextGreaterElement(int n) {
	string nums = to_string(n);
	const int len = nums.length();
	int anchor = -1;
	for(int i = len-1; i > 0; i--) {
	if(nums[i] > nums[i-1]) {
	anchor = i-1;
	break;
	}
	}
	if(anchor == -1) {
	return -1;
	}
	//>> sort the part after anchor
	sort(nums.begin()+anchor+1, nums.end());
	//>> swap the anchor with the number which is bigger and cloest to anchor
	for(int i = anchor+1; i < len; i++) {
	if(nums[i] > nums[anchor]) {
	swap(nums[i], nums[anchor]);
	break;
	}
	}
	//>> find the ans
	long ans = stol(nums);
	return ans > INT_MAX ? -1 : (int)ans;
	}
	};

view raw nextGreaterElement3_1.cpp hosted with ❤ by GitHub

Java

	class Solution {
	public int nextGreaterElement(int n) {
	char[] nums = String.valueOf(n).toCharArray();
	int anchor = -1;
	for(int i = nums.length-1; i > 0; i--) {
	if(nums[i] > nums[i-1]) {
	anchor = i-1;
	break;
	}
	}
	if(anchor == -1) {
	return -1;
	}
	//>> sort the part after anchor
	Arrays.sort(nums, anchor+1, nums.length);
	//>> swap the anchor with the number which is bigger and cloest to anchor
	for(int i = anchor + 1; i < nums.length; i++) {
	if(nums[i] > nums[anchor]) {
	char tmp = nums[i];
	nums[i] = nums[anchor];
	nums[anchor] = tmp;
	break;
	}
	}
	//>> find the answer
	long ans = Long.valueOf(String.valueOf(nums));
	return ans > Integer.MAX_VALUE ? -1 : (int)ans;
	}
	}

view raw nextGreaterElement3.java hosted with ❤ by GitHub

kotlin

	class Solution {
	fun nextGreaterElement(n: Int): Int {
	val s = n.toString().toCharArray()
	var anchor1 = s.lastIndex-1
	while(anchor1 >= 0 && s[anchor1] >= s[anchor1+1]) {
	--anchor1
	}
	if(anchor1 < 0){
	return -1
	}
	var anchor2 = s.lastIndex
	while(anchor2 >= 0 && s[anchor2] <= s[anchor1]) {
	--anchor2
	}
	s[anchor1] = s[anchor2].also { s[anchor2] = s[anchor1] }
	++anchor1
	anchor2 = s.lastIndex
	while(anchor1 < anchor2) {
	s[anchor1] = s[anchor2].also { s[anchor2] = s[anchor1] }
	++anchor1
	--anchor2
	}
	val ans = String(s).toLong()
	return if(ans > Int.MAX_VALUE) -1 else ans.toInt()
	}
	}

view raw next_greater_element_III.kt hosted with ❤ by GitHub

C++有內建 next_permutation 的函式，也可以拿來使用

	class Solution {
	public:
	int nextGreaterElement(int n) {
	string nums = to_string(n);
	next_permutation(nums.begin(), nums.end());
	long ans = stol(nums);
	return (ans > INT_MAX || n >= (int)ans) ? -1 : (int)ans;
	}
	};

view raw nextGreaterElement3_2.cpp hosted with ❤ by GitHub