229. Stack sorting

Leave a comment

September 3, 2016 by oneOokay

15分钟写出来了,一次过,有点开心嘻嘻嘻

我的基本思路是:

最初的第一步想到用另一个stack B来存数,经过一系列的逻辑处理后把所有的数都放到B里头,再倒回A。所以这个时候要求B里头应该是一个递减栈,栈的top为min。

然后A.peek 与 B.peek相比较:

  • 若A.peek小于B.peek,则 A.pop, push 入 B。
  • 若A.peek大于B.peek,则A.pop存入一个tmp,B需要pop那个比tmp小的值,放到哪里去啊?不让其他的数据结构,就直接放回A里好了。当B不为空的时候一直loop,pop,直到找到比tmp大的值,此时不pop了,把tmp push入B。继续进行A.peek和B.peek的比较。

当A为空时,说明所有元素已经到B中去了,B已经为一个单调减栈,把B中的元素倒回A,A就成为了一个单调增栈。

看了一下九章:我觉得我的比较好,感觉他多倒了一次。它的最后一次其实A已经有序了,然后还是需要重新倒入B中,再倒回A。

九章的区别在:上面黄色字换成把tmp push 入A,再把B中剩下的所有pop出来push入A,再重新进行循环。一直到把大概是把A从上到下逐渐变有序。

public void stackSorting(Stack<Integer> A) {
if (A == null || A.size() <= 1) {
return;
}

Stack<Integer> B = new Stack<Integer>();
while (!A.isEmpty()){
int aPeek = A.peek();
if (B.isEmpty() || B.peek() > aPeek){
B.push(A.pop());
}else {
int current = A.pop();
while (!B.isEmpty() && B.peek() < current){
A.push(B.pop());
}
B.push(current);
}
}

while(!B.isEmpty()){
A.push(B.pop());
}
}

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: