LeetCode 969. 煎饼排序

示例 1：

输入：[3,2,4,1]
输出：[4,2,4,3]
解释：
我们执行 4 次煎饼翻转，k 值分别为 4，2，4，和 3。
初始状态 A = [3, 2, 4, 1]
第一次翻转后 (k=4): A = [1, 4, 2, 3]
第二次翻转后 (k=2): A = [4, 1, 2, 3]
第三次翻转后 (k=4): A = [3, 2, 1, 4]
第四次翻转后 (k=3): A = [1, 2, 3, 4]，此时已完成排序。 
示例 2：

输入：[1,2,3]
输出：[]
解释：
输入已经排序，因此不需要翻转任何内容。
请注意，其他可能的答案，如[3，3]，也将被接受。

class Solution {
public:
    vector<int> pancakeSort(vector<int>& A) {
        int i,j = A.size()-1,k;
        vector<int> ans;
        while(j>=1)
        {
        	i = findmax(A,j);
        	if(i != 0)//不在队首，翻2次，先翻到队首
    		{
    			ans.push_back(i+1);
    			reverse(A.begin(), A.begin()+i+1);
    		}
    		ans.push_back(j+1);//在队首，直接翻到最后
    		reverse(A.begin(), A.begin()+j+1);
    		--j;
        }
        return ans;
    }
    int findmax(vector<int>& A, int &j)
    {//找未排序的最大数的下标
    	int m = INT_MIN, idx;
    	for(int i=0; i<=j; ++i)
    		if(A[i] > m)
    		{
    			m = A[i];
    			idx = i;
    		}
		return idx;
    }
};