题目描述

给定一个数组 A，我们可以做如下的 薄饼翻转 ：我们选择一个正整数 k <= A.length，然后将 A 的前 k 个元素的顺序颠倒。我们希望能做 0 次或多次的 薄饼翻转（一次接一次）来将数组 A 排序。

返回一组对应排序数组 A 的 k 值序列。任何在 10 * A.length 次翻转后能将数组排序的可行答案都是正确的。

样例

输入：[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], 已经排好序了。

输入：[1,2,3]
输出：[]
解释：输入已经是有序的，所以不需要任何翻转。
注意其他答案，例如 [3, 3] 也可以被接受。

注意

• 1 <= A.length <= 100
• A[i] 是 [1, 2, ..., A.length] 的一个排列。

算法

(倒推) $O(n^2)$

1. 假设我们现在面对一个有序的数组 cur，期望通过以上操作将其变回数组 A。
2. 我们从数组末尾开始往开头匹配，如果 cur 的当前元素 cur[i] 与 A[i] 不一致，则在 i 之前的元素中检索 A[i]。
3. 找到 k 使得 cur[k] = A[i]；如果 k = 1，则直接做一次翻转即可将 cur[k] 放到 cur[i] 处；否则需要先将 cur[k] 放到 cur[1] 处，然后再将 cur[1] 放到 cur[i] 处。
4. 如此循环直到完成所有数字的匹配，将 ans 数组倒置就是答案。

时间复杂度

• 共有 $O(n)$ 个位置需要匹配，每次检索和移动数组同样需要 $O(n)$ 的时间，故总时间复杂为 $O(n^2)$。

空间复杂度

• 需要一个当前数组 cur 和一个答案数组，故总空间复杂度为 $O(n)$。

C++ 代码

class Solution {
public:
    vector<int> pancakeSort(vector<int>& A) {
        int n = A.size();
        vector<int> cur(n), ans;

        for (int i = 0; i < n; i++)
            cur[i] = i + 1;

        for (int i = n - 1; i >= 0; i--) {
            if (cur[i] != A[i]) {
                int k = -1;
                for (int j = 0; j < i; j++)
                    if (cur[j] == A[i]) {
                        k = j;
                        break;
                    }

                if (k > 0) {
                    reverse(cur.begin(), cur.begin() + k + 1);
                    ans.push_back(k + 1);
                }
                reverse(cur.begin(), cur.begin() + i + 1);
                ans.push_back(i + 1);
            }
        }
        reverse(ans.begin(), ans.end());

        return ans;
    }
};