設(shè)計(jì)一個(gè)支持 push，pop，top 操作，并能在常數(shù)時(shí)間內(nèi)檢索到最小元素的棧。

• push(x) – 將元素 x 推入棧中。
• pop() – 刪除棧頂?shù)脑亍?/li>
• top() – 獲取棧頂元素。
• getMin() – 檢索棧中的最小元素。

示例：

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.

方法一：使用輔助棧
使用輔助棧來存儲(chǔ)當(dāng)前數(shù)據(jù)棧的最小元素，即插入元素時(shí) 同時(shí)維護(hù)數(shù)據(jù)棧和輔助棧，數(shù)據(jù)棧正常放入元素；輔助棧的棧頂則保存當(dāng)前數(shù)據(jù)棧中最小的元素即可

實(shí)現(xiàn)如下：

class MinStack {
public:/** initialize your data structure here. */MinStack() {}void push(int x) {data.push(x);//維護(hù)輔助棧//如果當(dāng)前元素大小 小于輔助棧頂元素，則將當(dāng)前元素放入輔助棧中if (min_stack.empty()) {min_stack.push(x);} else {if (x < min_stack.top()) {min_stack.push(x);} else {min_stack.push(min_stack.top());}}}void pop() {data.pop();min_stack.pop();}int top() {return data.top();}int getMin() {return min_stack.top();}
private:stack<int> min_stack;stack<int> data;
};

方法二：不用輔助棧
插入元素時(shí)同時(shí)，兩個(gè)為一個(gè)單元，第二個(gè)為棧最小元素，第一個(gè)為要插入的元素

實(shí)現(xiàn)如下:

class MinStack {
public:/** initialize your data structure here. */MinStack() {}void push(int x) {if(data.empty()){data.push(x);data.push(x);} else {if (x >= data.top()) {int tmp = data.top();data.push(x);data.push(tmp);} else {data.push(x);data.push(x);}}}void pop() {data.pop();data.pop();}//返回時(shí)需先保存棧頂?shù)淖钚≡?/span>int top() {int tmp = data.top();data.pop();int result = data.top();data.push(tmp);return result;}int getMin() {return data.top();}
private:stack<int> data;
};

總結(jié)

以上是生活随笔為你收集整理的leetcode-155 最小栈的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。