免费seo工具大全_农村自建房设计图纸_站长工具权重查询_网盘资源共享网站

题意：给定一个数组，用pancake操作使得整个数组从小到大排列，返回pancake操作的数组
每一次pancake操作是把[0,k-1]的元素reverse

https://leetcode.com/problems/pancake-sorting/description/

解法：我首先先想到需要有个指针移动，让每一个数字都在正确的位置上。从前往后的指针不合适，因为每一次pancake操作都会让从前往后的元素乱序。所以应该从后往前去遍历数组，让数组有序

指针i, j, i从后往前遍历，j遍历$[0,i]$，记录下最大值的位置pos,把[0:pos]数组进行pancake操作，这样最大值成了$nums[0]$，再reverse一下，那么nums[i]的元素就确定下来了。

class Solution {
public:vector<int> pancakeSort(vector<int>& arr) {vector<int> res;for(int i = arr.size() - 1; i >= 0; i--) {int pos = 0;for(int j = 0; j <= i; j++) {if(arr[j] > arr[pos]) {pos = j;}}if(pos == i) {continue;}reverse(arr.begin(), arr.begin()+pos+1);res.push_back(pos+1);reverse(arr.begin(), arr.begin()+i+1);res.push_back(i+1);}return res;}
};

时间复杂度$O(n^2)$
空间复杂度$O(1)$