題目:定義棧的數(shù)據(jù)結(jié)構(gòu)泼疑,要求添加一個(gè)min函數(shù)链快,能夠得到棧的最小元素。要求函數(shù)min邪媳、push以及pop的時(shí)間復(fù)雜度都是O(1).
<pre><code>`
class StackMin {
var stack:[Int] = []
var minStack:[Int] = []
func push(node:Int) {
stack.append(node)
if minStack.count > 0 {
let lastNode:Int = minStack[minStack.count-1]
if lastNode < node {
minStack.append(lastNode)
} else {
minStack.append(node)
}
} else {
minStack.append(node)
}
}
func pop() -> Int? {
let index:Int = minStack.count - 1
if index < 0 {
return nil
}
let value:Int = stack[index]
stack.remove(at: index)
minStack.remove(at: index)
return value
}
func min() -> Int? {
let index:Int = minStack.count - 1
if index < 0 {
return nil
}
let value:Int = minStack[index]
return value
}
}`</code></pre>
測(cè)試代碼:
<pre><code>`
var minStack:StackMin = StackMin()
minStack.push(node: 30)
minStack.push(node: 40)
minStack.push(node: 20)
minStack.push(node: 10)
minStack.push(node: 50)
print(minStack.stack)
print(minStack.minStack)
print("最小值--(minStack.min()!)")
print("pop--(minStack.pop()!)")
print("最小值--(minStack.min()!)")
print("pop--(minStack.pop()!)")
print("最小值--(minStack.min()!)")`</code></pre>