幾百年沒有更新Blog了
前幾天看到這題就順手寫了一下
用兩個stack的作法好像還蠻簡單的
但只用一個stack做就蠻炫的，discussion上有靠diff的方式只花了一個stack
簡單來說大概就是在遇到更小data push的時候更新min
pop掉的時候在用diff回到先前的 min
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
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; } }; |
