Given a list of integers, which denote a permutation.

Find the previous permutation in ascending order.

Note

The list may contains duplicate integers.

Example

For [1,3,2,3], the previous permutation is [1,2,3,3]

For [1,2,3,4], the previous permutation is [4,3,2,1]

 public class Solution {

     /**

      * @param nums: A list of integers

      * @return: A list of integers that's previous permuation

      */

     public ArrayList<Integer> previousPermuation(ArrayList<Integer> nums) {

         // write your code

         if (nums==null || nums.size()==0) return nums;

         int i = nums.size()-2;

         for (; i>=0; i--) {

             if (nums.get(i) > nums.get(i+1)) break;

         }

         if (i >= 0) {

             int j=i;

             for (; j<=nums.size()-2; j++) {

                 if (nums.get(j+1) >= nums.get(i)) break;

             }

             int temp = nums.get(j);

             nums.set(j, nums.get(i));

             nums.set(i, temp);

         }

         reverse(nums, i+1);

         return nums;

     }

     public void reverse(ArrayList<Integer> nums, int k) {

         int l = k, r = nums.size()-1;

         while (l < r) {

             int temp = nums.get(l);

             nums.set(l, nums.get(r));

             nums.set(r, temp);

             l++;

             r--;

         }

     }

 }