JIAKAOBO

LeetCode

venmo
wechat

感谢赞助!

  • ㊗️
  • 大家
  • offer
  • 多多！

Problem

Given an array of positive integers arr (not necessarily distinct), return the lexicographically largest permutation that is smaller than arr, that can be made with exactly one swap (A swap exchanges the positions of two numbers arr[i] and arr[j]). If it cannot be done, then return the same array.

Example 1:

Input: arr = [3,2,1]
Output: [3,1,2]
Explanation: Swapping 2 and 1.

Example 2:

Input: arr = [1,1,5]
Output: [1,1,5]
Explanation: This is already the smallest permutation.

Example 3:

Input: arr = [1,9,4,6,7]
Output: [1,7,4,6,9]
Explanation: Swapping 9 and 7.

Example 4:

Input: arr = [3,1,1,3]
Output: [1,3,1,3]
Explanation: Swapping 1 and 3.

Code

class Solution {
    public int[] prevPermOpt1(int[] arr) {
        // 第一个升序
        int index = arr.length - 2;
        while(index >= 0 && arr[index] <= arr[index + 1]) {
            index--;
        }

        if(index < 0) return arr;

        int nextIndex = index + 1;
        int num = arr[nextIndex];
        for(int i = index + 1; i < arr.length; i++) {
            // 比arr[index]小的数中最大的一个
            if(arr[i] > num && arr[i] < arr[index]){
                nextIndex = i;
                num = arr[i];
            }
        }

        arr[nextIndex] = arr[index];
        arr[index] = num;
        return arr;
    }
}