Min Stack

全栈程序员-站长 • 2021年9月8日上午8:00 • 未分类 • 阅读 54

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，pop，top以及以常数时间检索里面的最小元素

思路：

1、用两个stack来解决：第一个stack用来正常进行stack的push，pop和top操作；另外一个min_stack用来存储最小元素.每次对stack进行pop或者push时，也对min_stack进行相应操作。

2、第二个min_stack可以进行优化：不一定每个最小元素都要入栈min_stack, push的时候，只入栈比当前min小或者相等的值就可以了。pop的时候，要比较待pop元素和min_stack中top的大小。如果待pop元素和min_stack的top元素相等，则将min stack进行pop。

代码如下：

class MinStack {  
private:  
    std::stack<int> stack;  
    std::stack<int> min_stack;  
public:  
    void push(int x) {  
        stack.push(x);  
        if (min_stack.empty() || ((!min_stack.empty()) && x <= min_stack.top())) {  //NOTE: 是“小于等于”，不是“小于”  
            min_stack.push(x);  
        }  
    }  
      
    void pop() {  
        if (!stack.empty()) {  
            if (stack.top() == min_stack.top())  
                min_stack.pop();  
            stack.pop();  
        }  
    }  
      
    int top() {  
        if (!stack.empty())  
            return stack.top();  
    }  
      
    int getMin() {  
        if (!min_stack.empty())  
            return min_stack.top();  
    }  
};

　或：

class MinStack {
public:
    void push(int x) {
        if (stk1.empty() || x <= stk2.top())
            stk2.push(x);
        stk1.push(x);
    }

    void pop() {
        if (stk1.top() == stk2.top())
            stk2.pop();
        stk1.pop();
    }

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

    int getMin() {
        return stk2.top();
    }
private:
    stack<int> stk1; 
    stack<int> stk2;
};

　　或者：using two vectors

class MinStack {
public:
    vector<int> stack; 
    vector<int> stmin = {INT_MAX};
    void push(int x) {
        if(x <= stmin[stmin.size() - 1]) stmin.push_back(x);
        stack.push_back(x);
    }

    void pop() {
        if(stack[stack.size() - 1] == stmin[stmin.size() - 1]) stmin.pop_back();
        stack.pop_back();
    }

    int top() {
        if(stack.size() == 0) return 0;
        return stack[stack.size() - 1];
    }

    int getMin() {
        return stmin[stmin.size() - 1];
    }
};

转载于:https://www.cnblogs.com/carsonzhu/p/4684558.html

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/109380.html原文链接：https://javaforall.net