Leetcode 155 - Min Stack（Stack）

题意

设计一个stack，满足push, pop, top,getMin。 要求getMin时间复杂度为 O(1) 。

思路

主要处理的就是getMin。 我们的栈维护两个值：当前元素x，和到当前元素的最小值MIN。 每次push一个元素的时候更新MIN。

代码

class MinStack { private: struct node { int x, MIN; node(int a, int b) : x(a), MIN(b) {} }; stack<node> s; public: /** initialize your data structure here. */ MinStack() { while (s.size()) s.pop(); } void push(int x) { if (s.empty()) s.push(node(x, x)); else s.push(node(x, min(x, (s.top()).MIN))); } void pop() { s.pop(); } int top() { return (s.top()).x; } int getMin() { return (s.top()).MIN; } }; /** * 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(); */