#include<cstdio> #include<queue> using namespace std; int a[1000010],n; int main(){ while(~scanf("%d",&n)){ for(int i=1;i<=n;i++){ a[i]=n-i+1; } int i=1,j=n,k=0; deque<int> q; int res=0; while(i<=j){ if(!k){ q.push_back(a[i]); int sz=q.size(); res=max(res,sz); a[i]=a[j]; i++,j--; }else{ int top=q.front(); q.pop_front(); int tmp=a[i]; a[i]=top; q.push_back(tmp); int sz=q.size(); res=max(res,sz); i++; } k=k^1; } if(a[i-1]==q.back()) q.pop_back(); while(!q.empty()){ if(!k){ int top=q.back(); q.pop_back(); a[i]=top; i++,k=k^1; }else{ int top=q.front(); q.pop_front(); a[i]=top; i++,k=k^1; } } for(int i=1;i<=n;i++){ printf("%d ",a[i]); } printf("\n"); } } 时间复杂度O(n)肯定没问题。 如果n很小的话，队列元素很少，空间复杂度可以看成是常数级别O(1)。 如果n为10^6级别的话，则队列最大元素个数可用res那个变量求出，大概在3*10^5左右。n为10^5, 则res为3*10^4左右。。 总之就是双指针在使用的过程中，覆盖的元素会越来越多，因而只能用队列来保存。如果n为10^6级别， 纯O(1)做法，不会覆盖别的元素的做法还真没想出来。