首页 > 考试 > 其他 >

【一天一道LeetCode】#155. Min Stack

2016-07-09

题目大意:实现一个最小栈,在常量时间内完成push,pop,top和getmin等操作,解题思路:用两个栈,一个栈存储所有的数字,另一个栈存储最小数。

(一)题目

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.

top() – 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.top(); –> Returns 0.
minStack.getMin(); –> Returns -2.

(二)解题

题目大意:实现一个最小栈,在常量时间内完成push,pop,top和getmin等操作

解题思路:用两个栈,一个栈存储所有的数字,另一个栈存储最小数。
具体思路见代码:

class MinStack {
public:
    /** initialize your data structure here. */
    stack datastack;//存储数据
    stack minstack;//存储最小栈
    MinStack() {

    }
    void push(int x) {
        datastack.push(x);//压入数据
        if(minstack.empty()) minstack.push(x);//如果最小栈为空直接压入
        else if(x<=minstack.top()) minstack.push(x);//如果当前压入的值小于等于最小栈的栈顶元素,则压入最小栈
    }

    void pop() {
        if(datastack.top()==minstack.top()) minstack.pop();//如果数据栈和最小栈的栈顶元素相等,则最小栈栈顶元素弹出
        datastack.pop();//数据栈弹出元素

    }

    int top() {
        return datastack.top();//返回栈顶元素
    }

    int getMin() {
        return minstack.top();//返回最小栈栈顶元素
    }
};
/**
 * 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();
 */
相关文章
最新文章
热点推荐