一、題目
??請?jiān)O(shè)計(jì)一個(gè)棧，除了常規(guī)棧支持的 pop 與 push 函數(shù)以外，還支持 min 函數(shù)，該函數(shù)返回棧元素中的最小值。執(zhí)行 push、pop 和 min 操作的時(shí)間復(fù)雜度必須為 O(1)。
??點(diǎn)擊此處跳轉(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.文章來源：http://www.zghlxwxcb.cn/news/detail-693930.html
二、C# 題解
??要實(shí)現(xiàn) O(1) 復(fù)雜度的 min 函數(shù)，只需多使用一個(gè)數(shù)組記錄最小值即可：文章來源地址http://www.zghlxwxcb.cn/news/detail-693930.html
public class MinStack {
private List<int> data; // 存放棧數(shù)據(jù)
private List<int> mins; // 存放對應(yīng)棧的最小值
private int p; // 棧頂指針
/** initialize your data structure here. */
public MinStack() {
data = new List<int>(128);
mins = new List<int>(128);
p = -1;
}
public void Push(int x) {
data.Add(x);
if (p == -1) mins.Add(x);
else mins.Add(x < mins[p] ? x : mins[p]); // 比較 x 與 min，放入更小的一個(gè)
p++;
}
public void Pop() {
if (p == -1) return;
data.RemoveAt(p);
mins.RemoveAt(p);
p--;
}
public int Top() {
return data[p];
}
public int GetMin() {
return mins[p];
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.Push(x);
* obj.Pop();
* int param_3 = obj.Top();
* int param_4 = obj.GetMin();
*/
- 時(shí)間復(fù)雜度： O ( n ) O(n) O(n)。
- 空間復(fù)雜度： O ( 1 ) O(1) O(1)。
到了這里，關(guān)于LeetCode 面試題 03.02. 棧的最小值的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
