Leetcode-155Min Stack

155. Min Stack && 剑指offer-包含min函数的栈

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.

题解：

本题的要求是定义栈的数据结构，在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
我们来分析下介道题，首先我们定义一个栈s，用来实现栈的基本操作；本题要求在栈的数据结构中加入一个取栈中所含最小元素的min函数，所以我们再定义另一个栈min_s，专门用来存储和获取栈中最小的元素。

image.png
如图：
栈s用来实现栈基本操作，所以正常执行栈的成员函数功能；
最小栈min_s用来实现最小栈元素函数，所以只用来存储小于等于栈顶元素的元素；
然鹅，为什么等于min_s的栈顶元素时也要进栈呢？因为我们如果对栈s执行pop()操作，而s的栈顶元素又恰好是最小的元素，那么就要同时删除min_s的栈顶元素；如果不把等于min_s的栈顶元素进栈，那么在删除min_s的栈顶元素以后，min_s的栈顶元素就会变更为比原来的栈顶元素大的元素，更坏的情况下甚至会令最小栈为空，导致程序因为无法获取min_s的栈顶元素而崩溃（例如图中四步操作后，执行两次s.pop()操作）。

My Solution（C/C++完整实现）：

#include <cstdio>
#include <iostream>
#include <stack>

using namespace std;

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {

    }

    void push(int x) {
        if (min_s.empty() || min_s.top() >= x) {
            min_s.push(x);
        }
        s.push(x);
    }

    void pop() {
        if (!min_s.empty() && min_s.top() == s.top()) {
            min_s.pop();
        }
        s.pop();
    }

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

    int getMin() {
        return min_s.top();
    }
private:
    stack<int> s;
    stack<int> min_s;
};

int main() {
    MinStack m_s;
    m_s.push(0);
    printf("Top: %d ; ", m_s.top());
    printf("Min: %d \n", m_s.getMin());
    m_s.push(1);
    printf("Top: %d ; ", m_s.top());
    printf("Min: %d \n", m_s.getMin());
    m_s.push(0);
    printf("Top: %d ; ", m_s.top());
    printf("Min: %d \n", m_s.getMin());
    m_s.pop();
    printf("Top: %d ; ", m_s.top());
    printf("Min: %d \n", m_s.getMin());
    return 0;
}

结果：

Top: 0 ; Min: 0
Top: 1 ; Min: 0
Top: 0 ; Min: 0
Top: 1 ; Min: 0

My Solution（Python）:

def min_s(x, y):
    if x < y: return x
    else: return y
class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.Min_stack = []

    def push(self, x):
        """
        :type x: int
        :rtype: void
        """
        self.stack.append(x)
        if self.Min_stack != []:
            x = min_s(x, self.Min_stack[-1])
        self.Min_stack.append(x)


    def pop(self):
        """
        :rtype: void
        """
        self.Min_stack.pop()
        return self.stack.pop()
        
        
    def top(self):
        """
        :rtype: int
        """
        x = self.stack.pop()
        self.stack.append(x)
        return x

    def getMin(self):
        """
        :rtype: int
        """
        Min = self.Min_stack.pop()
        self.Min_stack.append(Min)
        return Min


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()