原题(来源牛客网)
一个栈中元素的类型为整型,现在想将该栈从顶到底按从大到小的顺序排序,只许申请一个栈。除此之外,可以申请新的变量,但不能申请额外的数据结构。如何完成排序?
解法
思想
申请一个辅助栈,应让该辅助栈成为一个单调栈,可以这样做:
原栈每次弹出一个元素,如果比辅助栈顶元素小(或辅助栈内为空)就直接压入辅助栈,如果比辅助栈顶元素大,则先保留该元素,将辅助栈内的比该元素小的元素压回原栈,再将该元素压入辅助栈,如此往复,直到辅助栈成为一个栈顶到栈底递增的栈,再将辅助栈内的元素压回原栈。
代码
class Solution {
public void sortStackByStack(Stack<Integer> stack) {
Stack<Integer> help = new Stack<>();
while(!stack.isEmpty()){
int cur = stack.pop();
while(!help.isEmpty()&&help.peek()<cur){
stack.push(help.pop());
}
help.push(cur);
}
while(!help.isEmpty()){
stack.push(help.pop());
}
}
}
原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/%e7%94%a8%e4%b8%80%e4%b8%aa%e6%a0%88%e5%ae%9e%e7%8e%b0%e5%8f%a6%e4%b8%80%e4%b8%aa%e6%a0%88%e7%9a%84%e6%8e%92%e5%ba%8f/