Monday, February 18, 2019

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

Code (Java):
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