幾百年沒有更新Blog了
前幾天看到這題就順手寫了一下
用兩個stack的作法好像還蠻簡單的
但只用一個stack做就蠻炫的,discussion上有靠diff的方式只花了一個stack
簡單來說大概就是在遇到更小data push的時候更新min
pop掉的時候在用diff回到先前的 min
class MinStack { public: /** initialize your data structure here. */ long min; stack<long> my_stack; MinStack() { } void push(int x) { if(this->my_stack.empty()) { min = x; my_stack.push(0); } else { my_stack.push(x-min); if(x<min) min = x; } } void pop() { if(this->my_stack.top() < 0) this->min -= this->my_stack.top(); this->my_stack.pop(); } int top() { if(this->my_stack.top() > 0) return this->my_stack.top() + this->min; else return this->min; } int getMin() { return this->min; } };