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
class Solution { public int nextGreaterElement(int n) { String s = n + ""; char[] arr = s.toCharArray(); // step 1: go from end and find the descreasing number // int i = s.length() - 2; while (i >= 0 && s.charAt(i) >= s.charAt(i + 1)) { i--; } if (i < 0) { return -1; } int j = i + 1; while (j < s.length() && s.charAt(j) > s.charAt(i)) { j++; } j--; swap(arr, i, j); reverse(arr, i + 1); String ans = new String(arr); Long l = Long.parseLong(ans); if (l >= Integer.MAX_VALUE) { return -1; } return Integer.parseInt(ans); } private void swap(char[] arr, int i, int j) { char temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } private void reverse(char[] arr, int start) { int end = arr.length - 1; while (start < end) { swap(arr, start, end); start++; end--; } } }
No comments:
Post a Comment