面试题 03.05. 栈排序
栈排序。 编写程序，对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。该栈支持如下操作：push、pop、peek 和 isEmpty。当栈为空时，peek 返回 -1。
示例1:
输入： ["SortedStack", "push", "push", "peek", "pop", "peek"] [[], [1], [2], [], [], []] 输出： [null,null,null,1,null,2]
示例2:
输入： ["SortedStack", "pop", "pop", "push", "pop", "isEmpty"] [[], [], [], [1], [], []] 输出： [null,null,null,null,null,true]
说明:
原站题解
golang 解法, 执行用时: 4 ms, 内存消耗: 6.6 MB, 提交时间: 2022-11-30 18:47:39
type SortedStack struct {
sortedData []int
}
func Constructor() SortedStack {
return SortedStack{make([]int, 0)}
}
func (this *SortedStack) Push(val int) {
i := len(this.sortedData)
if i == 0 || this.sortedData[i-1] <= val {
this.sortedData = append(this.sortedData, val)
return
}
for i != 0 && this.sortedData[i-1] > val {
i--
}
this.sortedData = append(this.sortedData[:i], append([]int{val}, this.sortedData[i:]...)...)
}
func (this *SortedStack) Pop() {
if this.IsEmpty() {
return
}
this.sortedData = this.sortedData[1:]
}
func (this *SortedStack) Peek() int {
if this.IsEmpty() {
return -1
}
return this.sortedData[0]
}
func (this *SortedStack) IsEmpty() bool {
return len(this.sortedData) == 0
}
/**
* Your SortedStack object will be instantiated and called as such:
* obj := Constructor();
* obj.Push(val);
* obj.Pop();
* param_3 := obj.Peek();
* param_4 := obj.IsEmpty();
*/
python3 解法, 执行用时: 52 ms, 内存消耗: 16.3 MB, 提交时间: 2022-11-30 18:45:04
import heapq
class SortedStack:
def __init__(self):
self.stack = list()
heapq.heapify(self.stack)
def push(self, val: int) -> None:
heapq.heappush(self.stack, val)
def pop(self) -> None:
if not self.isEmpty():
ref = heapq.heappop(self.stack)
return ref
def peek(self) -> int:
if self.isEmpty():
return -1
ref = heapq.heappop(self.stack)
heapq.heappush(self.stack, ref)
return ref
def isEmpty(self) -> bool:
return len(self.stack) == 0
# Your SortedStack object will be instantiated and called as such:
# obj = SortedStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.peek()
# param_4 = obj.isEmpty()
python3 解法, 执行用时: 608 ms, 内存消耗: 16.5 MB, 提交时间: 2022-11-30 18:43:33
class SortedStack:
def __init__(self):
self.stack = list()
def push(self, val: int) -> None:
t = list()
while self.stack and self.stack[-1] < val:
t.append(self.stack.pop())
self.stack.append(val)
while t:
self.stack.append(t.pop())
def pop(self) -> None:
if not self.isEmpty():
self.stack.pop()
def peek(self) -> int:
if self.isEmpty():
return -1
return self.stack[-1]
def isEmpty(self) -> bool:
return len(self.stack) == 0
# Your SortedStack object will be instantiated and called as such:
# obj = SortedStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.peek()
# param_4 = obj.isEmpty()
javascript 解法, 执行用时: 104 ms, 内存消耗: 43.9 MB, 提交时间: 2022-11-30 18:41:15
var SortedStack = function() {
this.sortStask = [];
};
/**
* @param {number} val
* @return {void}
*/
SortedStack.prototype.push = function(val) {
let i = this.sortStask.length;
while(this.sortStask[i - 1] < val) i--;
this.sortStask.splice(i, 0, val);
};
/**
* @return {void}
*/
SortedStack.prototype.pop = function() {
return this.sortStask.pop();
};
/**
* @return {number}
*/
SortedStack.prototype.peek = function() {
return this.sortStask.length ? this.sortStask[this.sortStask.length - 1] : -1;
};
/**
* @return {boolean}
*/
SortedStack.prototype.isEmpty = function() {
return !this.sortStask.length;
};
/**
* Your SortedStack object will be instantiated and called as such:
* var obj = new SortedStack()
* obj.push(val)
* obj.pop()
* var param_3 = obj.peek()
* var param_4 = obj.isEmpty()
*/