設(shè)計(jì)一個(gè)支持push、pop搭儒、top 操作,并能在常數(shù)時(shí)間內(nèi)檢索到最小元素的棧.
- push(x) ------ 將元素 x 推入棧中
- pop() ------ 刪除棧頂?shù)脑?/li>
- top() ------ 獲取棧頂?shù)脑?/li>
- getMin() ------ 檢索棧中的最小元素
摘一個(gè)示例做個(gè)說(shuō)明.
示例 1：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
輸出：
[null,null,null,null,-3,null,0,-2]
解釋?zhuān)?MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
條件分析:
- 棧設(shè)計(jì),就是所謂的壓入棧,彈出棧操作
- 最小元素獲取 -> 需要快速獲取最小值
解決思路1:
- 根據(jù)分析1,采用數(shù)據(jù)結(jié)構(gòu)數(shù)組進(jìn)行操作
- 設(shè)計(jì)最小值
利用數(shù)組的特性進(jìn)行壓入钠龙、彈出操作,設(shè)計(jì)最小值屬性,直接返回
class MinStack {
/// 棧數(shù)據(jù)存儲(chǔ)
var data: [Int] = []
/// 最小值
var minNum: Int?
init() {
}
func push(_ val: Int) {
/// 入棧,數(shù)組加操作,然后對(duì)比最小值
self.data.append(val)
minNum = min(minNum ?? .max, val)
}
func pop() {
/// 出棧
let last = self.data.popLast()
/// 最小值判斷
if last == minNum {
minNum = self.data.min()
}
}
func top() -> Int {
return self.data.last!
}
func getMin() -> Int {
return minNum!
}
}
最小棧提交結(jié)果.jpg
測(cè)試用例:
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
考察要點(diǎn):
- 棧
- 設(shè)計(jì)
