Java Solution with in-line explanation


  • 2

    The same problem with https://leetcode.com/problems/next-permutation

    public class Solution {
        public int nextGreaterElement(int n) {
            char[] chars = (n + "").toCharArray();
            
            int l = chars.length;
            if (l < 2) return -1;
            int[] nums = new int[l];
            
            for (int i = 0; i < l; i++) nums[i] = chars[i] - '0';
            
            //Start from its last element, traverse backward to find the first one with index i that satisfy
           // nums[i-1] < nums[i]. So, elements from nums[i] to nums[l-1] is reversely sorted.
            int index = l - 1;
            while (index > 0) {
                if (nums[index - 1] < nums[index]) break;
                index--;
            }
            
            //To find the next permutation, we have to swap some numbers at different positions, 
            //to minimize the increased amount, we have to make the highest changed position
            // as high as possible. Notice that index larger than or equal to i is not possible as
            // nums[i,l-1] is reversely sorted. So, we want to increase the number at index i-1,
            // clearly, swap it with the smallest number between nums[i,l-1] that is larger than nums[i-1].
            // For example, original number is 121543321, we want to swap the '1' at position 2 with '2' at position 7.
            if (index == 0) {
                return -1;
            }
            else {
                //The last step is to make the remaining higher position part as small as possible,
               // we just have to reversely sort the nums[i,l-1]
                int val = nums[index - 1];
                int j = l - 1;
                while (j >= index){
                    if (nums[j] > val) break;
                    j--;
                }
                swap(nums, j, index - 1);
                
                reverse(nums, index, l - 1);
            }
            
            long result = 0;
            for (int i = 0; i < l; i++) {
                result = result * 10 + nums[i];
            }
            
            return result <= Integer.MAX_VALUE ? (int)result : -1;
        }
        
        public void swap(int[] nums, int i, int j){
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        
        public void reverse(int[] nums, int start, int end){   
            if (start > end) return;
            for (int i = start; i <= (end + start) / 2; i++)
                swap(nums, i, start + end - i);
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.