赞
踩
参考链接: 猿辅导、美团、字节面试题——双栈排序
给定一个乱序的栈,设计算法将其升序排列。
ps: 允许额外使用一个栈来辅助操作
输入
[4, 2, 1, 3]
输出
[1, 2, 3, 4]
使用一个辅助栈, 维护辅助栈为单调递增栈。
每次操作都保证辅助栈内元素有序, 最终返回辅助栈即可
算法流程
当原始栈不为空时, 执行如下操作:
每次从原始栈中取一个元素 cur, 与辅助栈顶元素 top 比较大小,
public class StackSort { class Solution { public Deque<Integer> stackSort(Deque<Integer> stack) { Deque<Integer> helpStack = new ArrayDeque<>(); while (!stack.isEmpty()) { int cur = stack.pollLast(); while (!helpStack.isEmpty() && cur < helpStack.peekLast()) { stack.offerLast(helpStack.pollLast()); } helpStack.offerLast(cur); } return helpStack; } } public static void main(String[] args) { Solution solution = new StackSort().new Solution(); Deque<Integer> stack = new ArrayDeque<>(); stack.offerLast(4); stack.offerLast(2); stack.offerLast(1); stack.offerLast(3); Deque<Integer> ans = solution.stackSort(stack); System.out.println(1); } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。