556.Next-Greater-Element-III

556. 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

代码

Approach #1 Liner Solution

class Solution {
public int nextGreaterElement(int n) {
char[] a = ("" + n).toCharArray();
// find a number in the back that's bigger than the front
int i = a.length - 2;
while (i >= 0 && a[i] >= a[i + 1]) {
i--;
}
if (i < 0) {
return -1;
}
// 1321
// Find a number in the back that's bigger than the number up here
int j = a.length - 1;
while (j >= 0 && a[j] <= a[i]) {
j--;
}
swap(a, i, j);
reverse(a, i + 1);
try {
return Integer.parseInt(new String(a));
} catch(Exception e) {
return -1;
}
}
private void reverse(char[] a, int start) {
int i = start, j = a.length - 1;
while (i < j) {
swap(a, i, j);
i++;
j--;
}
}
private void swap(char[] a, int i, int j) {
char temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
Approach 2: Brute Force (Time Limit Exceeded)
class Solution {
public String swap(String a, int i, int j) {
if (i == j) return s;
String s1 = s.substring(0, i);
String s2 = s.substring(i + 1, j);
String s3 = s.substring(j + 1);
return s1 + s.charAt(j) + s2 + s.charAt(i) + s3;
}
ArrayList<String> list = new ArrayList<>();
void permute(String a, int l, int r) {
int i;
if (l == r) {
list.add(a);
} else {
for (i = l; i <= r; i++) {
a = swap(a, l, i);
permute(a, l + 1, r);
a = swap(a, 1, i);
}
}
}
public int nextGreaterElement(int n) {
String s = "" + n;
permute(s, 0, s.length() - 1);
Collections.sort(list);
int i;
for (i = list.size() - 1; i >= 0; i--) {
if (list.get(i).equals("" + n)) {
break;
}
}
if (i == list.size() - 1) {
return -1;
} else {
return Integer.parseInt(list.get(i + 1));
}
}
}