1053. Previous Permutation With One Swap

1053. Previous Permutation With One Swap (Medium)

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

 

Example 1:

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

Example 2:

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

Example 3:

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

Example 4:

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

 

Note:

1. 1 <= A.length <= 10000
2. 1 <= A[i] <= 10000

Related Topics:
Array, Greedy

Solution 1.

// OJ: https://leetcode.com/problems/previous-permutation-with-one-swap/
// Author: github.com/lzl124631x
// Time: O(N^2)
// Space: O(1)
class Solution {
public:
    vector<int> prevPermOpt1(vector<int>& A) {
        int first = -1, second;
        for (int i = A.size() - 1; i > first; --i) {
            while (i - 1 > first && A[i - 1] == A[i]) --i;
            int j = i - 1;
            while (j > first && A[j] <= A[i]) --j;
            if (j > first) {
                first = j;
                second = i;
            }
        }
        if (first > -1) swap(A[first], A[second]);
        return A;
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/previous-permutation-with-one-swap/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    vector<int> prevPermOpt1(vector<int>& A) {
        stack<pair<int, int>> s;
        int first = -1, second = -1;
        for (int i = 0; i < A.size(); ++i) {
            while (s.size() && A[i] >= s.top().second) s.pop();
            if (s.size() && (s.top().first >= second || (s.top().first == first && A[i] != A[second]))) {
                first = s.top().first;
                second = i;
            }
            s.emplace(i, A[i]);
        }
        if (first > -1) swap(A[first], A[second]);
        return A;
    }
};

Solution 3.

// OJ: https://leetcode.com/problems/previous-permutation-with-one-swap/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    vector<int> prevPermOpt1(vector<int>& A) {
        int i = A.size() - 2;
        while (i >= 0 && A[i] <= A[i + 1]) --i;
        if (i < 0) return A;
        int j = i + 1;
        for (int k = i + 2; k < A.size() && A[k] < A[i]; ++k) {
            if (A[k] > A[j]) j = k;
        }
        swap(A[i], A[j]);
        return A;
    }
};

Solution 4.

// OJ: https://leetcode.com/problems/previous-permutation-with-one-swap/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    vector<int> prevPermOpt1(vector<int>& A) {
        int i = A.size() - 2;
        while (i >= 0 && A[i] <= A[i + 1]) --i;
        if (i < 0) return A;
        auto j = lower_bound(A.begin() + i + 1, A.end(), A[i]) - 1;
        auto k = lower_bound(A.begin() + i + 1, j, *j);
        swap(A[i], *k);
        return A;
    }
};