0969. Pancake Sorting

题目信息

题号:

0969

难度:

Medium

主题:

数组构造、前缀翻转、排序操作序列

原题:

LeetCode 0969

重点:

一次操作选择 k 并反转前 k 个元素;返回的操作序列执行后必须使数组升序,长度不得超过 10 * n,任意合法序列均可

题目重述

给定整数数组 arr,它是 1 至 arr.length 的一个排列。一次煎饼翻转可以选择整数 k,其中 1 <= k <= arr.length,并反转数组前 k 个元素的顺序。

请返回一组 k 值,使按返回顺序执行全部翻转后,数组变为严格递增顺序。返回操作数不得超过 10 * arr.length;不要求操作次数最少,任意满足限制的序列都可返回。

1 <= arr.length <= 100。

自建示例

两次翻转完成排序:

输入:arr = [3,1,2]
输出:[3,2]
解释:先翻转前 3 个元素得到 [2,1,3],再翻转前 2 个元素得到 [1,2,3]。其他不超过 30 次的合法操作序列也可以返回。

数组已经升序:

输入:arr = [1,2,3]
输出:[]
解释:不执行任何翻转时数组已经严格递增,空操作序列满足长度限制。