[leetcode] 155. Min Stack

[leetcode] 155. Min Stack

Description

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) – Push element x onto stack.pop() – Removes the element on top of the stack-() – Get the top element.getMin() – Retrieve the minimum element in the stack.Example:

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

分析

题目的意思是：实现MinStack的push,pop,top,tetrieving功能。

空间换时间最小栈只不过在原有栈的基础上增加了一个获取最小值的功能，我们可以用两个栈来模拟，第一个栈来模拟正常的栈的功能，第二个栈用来存储栈中的最小值。注意我们在pop和push的一点小小的改变。

代码

class MinStack {private: stack s1,s2;public: /** initialize your data structure here. */ MinStack() { } void push(int x) { s1.push(x); if(s2.empty()||x<=s2-()){ s2.push(x); } } void pop() { if(s1-()==s2-()) s2.pop(); s1.pop(); } int top() { return s1-(); } int getMin() { return s2-(); }};/** * Your MinStack object will be instantiated and called as such: * MinStack obj = new MinStack(); * obj.push(x); * obj.pop(); * int param_3 = obj-(); * int param_4 = obj.getMin(); */

参考文献

​​[LeetCode] Min Stack 最小栈​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。