題目鏈接

棧排序

題目描述

注意點

• 對棧進行排序使最小元素位于棧頂
• 最多只能使用一個其他的臨時棧存放數據
• 不得將元素復制到別的數據結構（如數組）中
• 棧中的元素數目在[0, 5000]范圍內

解答思路

• 本題是要實現一個小頂堆，可以直接使用PriorityQueue
• 如果要使用棧完成該結構，則需要在入棧時對棧中元素進行排序：如果入棧的val比棧頂元素小，則直接將val加入到棧中；如果入棧的val比棧頂元素大，則需要先將棧中元素彈出并存儲，直到val比棧頂元素小為止，然后將val加入到棧中，再將彈出的棧中元素按順序添加到棧中（保證棧中的元素始終按從小到大進行排序）

代碼

class SortedStack {Stack<Integer> stk;public SortedStack() {stk = new Stack<>();}public void push(int val) {List<Integer> list = new ArrayList<>();while (!stk.isEmpty() && val > stk.peek()) {list.add(stk.pop());}stk.push(val);for (int i = list.size() - 1; i >= 0; i--) {stk.push(list.get(i));}}public void pop() {if (!stk.isEmpty()) {stk.pop();}}public int peek() {return stk.isEmpty() ? -1 : stk.peek();}public boolean isEmpty() {return stk.isEmpty();}
}

關鍵點

• 無