辛苦上班一週後終於迎來小週末,今天的題目是 155. Min Stack。覺得 Leetcote 題目有種循序漸進的感覺,前一週先暖身熟悉一些STL用法,這週開始加入了一些 LinkedList/Stack 之類的資結概念,我想可以期待下週會開始出現一些演算法了(嘛。
今天的題目要求實作一個 MinStack 陣列,可以 push/pop/回傳 top/回傳目前 Stack 中的最小值。使用STL實作起來相當快速,不過如果想要自己寫 LinkedList Node 也行,我想這應該就是寫程式最有趣的地方,每個人的寫法都各不相同,也是另一種條條大路通羅馬的體現吧。
class MinStack {
vector<int> v;
vector<int> vmin;
public:
/** initialize your data structure here. */
MinStack() {
vmin.push_back(INT_MAX);
}
void push(int x) {
v.push_back(x);
if(x<=vmin.back())
vmin.push_back(x);
}
void pop() {
if(v.empty())
return;
if(v.back() == vmin.back())
vmin.pop_back();
v.pop_back();
}
int top() {
if(v.empty())
return 0;
return v.back();
}
int getMin() {
return vmin.back();
}
};