题目描述

 

 思路

跟昨天一样，用空间换时间，设立一个最小值栈，一个原始栈

• 初始化：两个栈x_stack,min_stack,初始压一个正无穷到min_stack中，后面遇到比它小的就压进去.
• push：x_stack正常压值进取，min_stack压相较来说的最小值.
• pop：两个栈一起出栈顶的值，很巧，这里，因为之前每次push两个栈都会压值进去，所以现在出栈不会有啥影响.
• top：返回x_stack栈顶的值.
• min：返回min_stack栈顶的值.

题解

 

class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> x_stack;
    stack<int> min_stack;
    MinStack() {
        min_stack.push(INT_MAX);
    }
    
    void push(int x) {
        x_stack.push(x);
        min_stack.push(std::min(min_stack.top(),x));
    }
    
    void pop() {
        x_stack.pop();
        min_stack.pop();
    }
    
    int top() {
        return x_stack.top();
    }
    
    int min() {
        return min_stack.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->min();
 */

 

效果

 

 question：如果只用一个栈能实现吗？可能用链表的结构？