【題目描述】
Given a list of integers, which denote a permutation.Find the previous permutation in ascending order.
Notice:The list may contains duplicate integers.
給定一個(gè)整數(shù)數(shù)組來(lái)表示排列摆寄，找出其上一個(gè)排列宇色。
注意：排列中可能包含重復(fù)的整數(shù)
【題目鏈接】
www.lintcode.com/en/problem/previous-permutation/
【題目解析】
這題就是next permutation的逆過(guò)程繁堡。首先找到從后往前遍歷，直到找到一個(gè)數(shù)（假設(shè)位置為i）比之它前一位數(shù)姓哿（即該位到數(shù)組的最后是一個(gè)遞增序列）涕癣，然后將i到數(shù)組最后的所有數(shù)按遞減排列彬祖。然后在這個(gè)遞增數(shù)列里面找到第一個(gè)比i－1位置上數(shù)小的數(shù)，交換兩個(gè)數(shù)的位置即可纽竣。如果i＝1則說(shuō)明之前的整個(gè)數(shù)組都是遞增序列墓贿，現(xiàn)在整個(gè)數(shù)組變?yōu)檫f減數(shù)列，正好是previous permutation蜓氨，因此不用再做任何其他操作聋袋。
【參考答案】
