题解 | #复杂链表的复制#

NC115 栈和排序
看了别人的才有的思路，整理一下以免忘啦~
解题思路：
重点是是一个1->n的序列排序，所以最大的就是n，用curmax来记录；
vis数组用于记录当前数是否被遍历；
result用于储存结果

import java.util.;
public class Solution {
/*
* 栈排序
* @param a int整型一维数组 描述入栈顺序
* @return int整型一维数组
*/
public int[] solve (int[] a) {
// write code here
int index=0;
int curmax=a.length;
boolean[] vis=new boolean[a.length+1];
int[] result=new int[a.length];
Stack<integer> stack=new Stack<>();
for(int i=0;i<a.length;i++){
stack.add(a[i]);
vis[a[i]]=true;
while(curmax>0&&vis[curmax]==true){ //如果最大元素已经在栈中，curmax--;
curmax--;
}
while(!stack.isEmpty()&&stack.peek()>=curmax){
result[index++]=stack.pop();
}
}
while(!stack.isEmpty()){
result[index++]=stack.pop();
}
return result;
}
}</integer>