31. Next Permutation (String) & 556. Next Greater Element III

31. Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1

My Solutions：

从右往左，找到第一个降序的index，e.g. 76253，找到2，index = 2

1。如果找不到，说明所有数字从右往左升序排列，e.g. 12345, 反转所有数字

2。如果找得到，从右往左找到第一个比这个index上的数大的数字，两者交换，再反转这个index

之后的数字。

e.g. 76253，找到3，变成76352。再反转这个index之后的数字，变成76325。

e.g. 762531，找到3，变成763521。再反转这个index之后的数字，变成763125。

class Solution {
    public void nextPermutation(int[] nums) {
        if (nums == null || nums.length < 2) return;
        int i = nums.length - 2;
        
        // 找到第一个降序的index
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        
        if (i >= 0) {
            int j = nums.length - 1;
            // 找到从后往前第一个大数
            while (j >= 0 && nums[j] <= nums[i]) {
                j--;
            }
            swap(nums,i,j);
        }
        reverse(nums, i + 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[] A, int start) {
        int i = start, j = A.length - 1;
        while (i < j) {
            swap(A, i, j);
            i++;
            j--;
        }
    }
}

Next Greater Element III

Given a positive integer n, find the smallest integer which has exactly the same digits existing in the integer n and is greater in value than n. If no such positive integer exists, return -1.

Note that the returned integer should fit in 32-bit integer, if there is a valid answer but it does not fit in 32-bit integer, return -1.

Example 1:

Input: n = 12
Output: 21

Example 2:

Input: n = 21
Output: -1

Constraints:

• 1 <= n <= 231 - 1

My Solutions:

和31题类似。

class Solution {
    public int nextGreaterElement(int n) {
        if (n < 10) return -1;
        List<Integer> nums = new ArrayList<>();
        while (n > 0) {
            nums.add(0, n % 10);
            n /= 10;
        }
        int len = nums.size(), i = len - 2;
        while (i >= 0 && nums.get(i) >= nums.get(i + 1)) i--;
        if (i == -1) return -1;
        
        int j = len - 1;
        while (j >= 0 && nums.get(j) <= nums.get(i)) j--;
        
        swap(nums, i, j);
        reverse(nums, i + 1);
        
        long res = 0;
        for (int num : nums) {
            res = res * 10 + num;
        }
        return res <= Integer.MAX_VALUE ? (int) res : -1;
    }

    private void swap(List<Integer> nums, int i, int j) {
        int temp = nums.get(i);
        nums.set(i, nums.get(j));
        nums.set(j, temp);
    }

    private void reverse(List<Integer> nums, int start) {
        int i = start, j = nums.size() - 1;
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }
}