leetcode_1053. Previous Permutation With One Swap

1053. Previous Permutation With One Swap

https://leetcode.com/problems/previous-permutation-with-one-swap/

题意：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.

解法：对于每个A，找到最右边的第一个逆序对{ A[i]>A[j] }，然后将A[i]和其后小于A[i]的最大的元素交换。

class Solution

{

public:

    vector<int> prevPermOpt1(vector<int>& A)

    {

        int pa=A.size()-,mina=A[A.size()-],pos=A.size()-;

        while(pa>=)

        {

            if(A[pa]>A[pa+])

            {

                pos=pa;

                break;

            }

            pa--;

        }

        if(pos==A.size()-)

            return A;

        int pos_=pos+,maxa=-,max_pos=-;

        while(pos_<A.size())

        {

            if(A[pos_]<A[pos]&&A[pos_]>maxa)

            {

                maxa=A[pos_];

                max_pos=pos_;

            }

            pos_++;

        }

        swap(A[pos],A[max_pos]);

        return A;

    }

};

巴特西

leetcode_1053. Previous Permutation With One Swap

最新文章

热门文章