leetcode Min Stack

题目链接

min-stack

题目描述(Description)

Min Stack

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.

带有最小值操作的栈

设计一个栈使其支持压入、弹出、返回栈顶元素和及时返回栈的最小元素。

• push(x) –把元素x压入栈中

• pop() –移除栈顶元素

• top() –得带栈顶元素

• getMin() –获得栈的最小元素

分析(Analysis)

本题用C++做非常简单，因为C++里的封装了stack的基本操作。

本题的难点在于如果获得最小元素，这里要求时间复杂度为O(1)，那么通过遍历的方法找最小值的方法在这里是行不通的。

我们可以通过维护一个minStack的栈，栈顶元素是当前栈里所有元素的最小值，只要把minStack的栈顶元素返回即可。

代码(Code)

class MinStack {
public:
    void push(int x) {
        s.push(x);
        if(minS.empty()||minS.top()>=x)
            minS.push(x);
    }

    void pop() {
        if(s.top()==minS.top())
                minS.pop();
        s.pop();
    }

    int top() {
        return s.top();
    }

    int getMin() {
        return minS.top();
    }
stack<int> s;
stack<int> minS;
};