Min Stack

文章目录

1. 1. Min Stack
   1. 1.1. 题目
   2. 1.2. 思路
   3. 1.3. 解题

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.

思路

利用两个栈，一个栈正常运行，另一个栈保存更新最小值。

解题

c++版

class MinStack {
public:
    stack<int> mstack;
    stack<int> minstack;
    void push(int x) {
        mstack.push(x);
        if(minstack.empty() || ((!minstack.empty()) && x <= minstack.top())) {  
            minstack.push(x);  
        }  
    }

    void pop() {
        if (!mstack.empty()) {  
            if (mstack.top() == minstack.top())  
                minstack.pop();  
            mstack.pop();  
        }  
    }

    int top() {
        if (!mstack.empty())  
            return mstack.top();
    }

    int getMin() {
        if (!minstack.empty())  
            return minstack.top();  
    }
};

python版

class MinStack:
    # @param x, an integer
    # @return an integer
    def __init__(self):
        self.stack=[]
        self.minstack=[]
        
    def push(self, x):
        self.stack.append(x)
        if len(self.minstack)==0 or x<=self.minstack[-1]:
            self.minstack.append(x)
        

    # @return nothing
    def pop(self):
        if(len(self.stack)!=0):
            if(self.stack[-1]==self.minstack[-1]):
                self.minstack.pop()
            self.stack.pop()

    # @return an integer
    def top(self):
        if(len(self.stack)!=0):
            return self.stack[-1]
        

    # @return an integer
    def getMin(self):
        if(len(self.minstack)!=0):
            return self.minstack[-1]