[LeetCode] 155. Min Stack 最小栈

2021年09月15日 阅读数:4
这篇文章主要向大家介绍[LeetCode] 155. Min Stack 最小栈,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.html

  • 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:java

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.

设计一个最小栈,实现push, pop, top, getMin四个功能。相比原来的栈多了一个功能,能够返回当前栈内的最小值。python

解法1:使用2个栈,栈1记录进来的数,栈2记录目前的最小值。当有新数push进来的时候,若是栈2为空或者这个数小于栈2顶上的值,就把这个数推入栈2。当pop的数正好等于最小值时,说明当前栈内的最小值变化了,要弹出这个最小值,记录的下一个最小值来到栈顶。app

解法2:只使用1个栈,用一个变量min_val记录当前的最小值,将当前最小值一同入栈,为节省空间,仅在当前最小值更改时才入栈。因此该栈的push和pop实际上多是两次。当新进来的数小于min_val时,把当前的min_val和新进来的数一块儿推入到栈,min_val变为这个新进来的数。当pop栈顶元素的时候,若是栈顶元素的值和min_val相等,那么就把它下面记录的以前最小值赋给min_val并弹出。post

解法3:也是使用1个栈,但栈中存的是当前值与最小值的差,用一个元素来记录,而后根据这个值能够计算出当前值和最小值。当栈顶元素为正时,表示当前元素比最小元素大,当前值为最小值+差值;当栈顶元素为负时,其表示的是当前元素值比以前最小值小,如今的最小值就是元素值。url

要注意重复值的push和pop。设计

Java: 2 Stackshtm

public class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<Integer>();
        minStack = new Stack<Integer>();
    }

    public void push(int number) {
        stack.push(number);
        if (minStack.empty() || minStack.peek >= number)
            minStack.push(number);
    }

    public int pop() {
        if (stack.peek().equals(minStack.peek()) ) 
            minStack.pop();
        return stack.pop();
    }

    public int min() {
        return minStack.peek();
    }
}

Java: 2 Stacksblog

public class MinStack {
    private Stack<Integer> s1 = new Stack<>();
    private Stack<Integer> s2 = new Stack<>();
    
    /** initialize your data structure here. */
    public MinStack() {}
    
    public void push(int x) {
        s1.push(x);
        if (s2.isEmpty() || s2.peek() >= x) s2.push(x);
    }
    
    public void pop() {
        // Cannot write like the following:
        // if (s2.peek() == s1.peek()) s2.pop();
        // s1.pop();
        int x = s1.pop();
        if (s2.peek() == x) s2.pop();
    }
    
    public int top() {
        return s1.peek();
    }
    
    public int getMin() {
        return s2.peek();
    }
}

Java: 1 Stackelement

public class MinStack {
    private int min_val = Integer.MAX_VALUE;
    private Stack<Integer> s = new Stack<>();
    
    /** initialize your data structure here. */
    public MinStack() {}
    
    public void push(int x) {
        if (x <= min_val) {
            s.push(min_val);
            min_val = x;
        }
        s.push(x);
    }
    
    public void pop() {
        if (s.pop() == min_val) min_val = s.pop();
    }
    
    public int top() {
        return s.peek();
    }
    
    public int getMin() {
        return min_val;
    }
}

Python: 2 Stacks

class MinStack:
  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)

  def pop(self):
    if self.top() == self.getMin():
        self.minStack.pop()
    return self.stack.pop()

  def top(self):
    return self.stack[-1]

  def getMin(self):
    return self.minStack[-1]  

Python: 1 Stack,最小值和元素一同入栈

class MinStack(object):

    def __init__(self):
        self.min = 2147483647
        self.stack = []

    def push(self, x):
        if x <= self.min:
            self.stack.append(self.min)
            self.min = x
        self.stack.append(x)

    def pop(self):
        peak = self.stack.pop()
        if peak == self.min:
            self.min = self.stack.pop()

    def top(self):
        return self.stack[-1]

    def getMin(self):
        return self.min

Python: 1 Stack,记录差值

class MinStack(object):

    def __init__(self):
        self.min = 2147483648
        self.stack = []

    def push(self, x):  
        if not self.stack:
            self.min = x
        self.stack.append(x - self.min)
        if x < self.min:
            self.min = x

    def pop(self):
        peak = self.stack.pop()
        if peak < 0:
            self.min = self.min - peak

    def top(self):
        if self.stack[-1] < 0:
            return self.min
        else:
            return self.min + self.stack[-1]

    def getMin(self):
        return self.min

C++: 2 Stacks

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {}
    
    void push(int x) {
        s1.push(x);
        if (s2.empty() || x <= s2.top()) s2.push(x);
    }
    
    void pop() {
        if (s1.top() == s2.top()) s2.pop();
        s1.pop();
    }
    
    int top() {
        return s1.top();
    }
    
    int getMin() {
        return s2.top();
    }
    
private:
    stack<int> s1, s2;
};

C++: 1 Stack

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {
        min_val = INT_MAX;
    }
    
    void push(int x) {
        if (x <= min_val) {
            st.push(min_val);
            min_val = x;
        }
        st.push(x);
    }
    
    void pop() {
        int t = st.top(); st.pop();
        if (t == min_val) {
            min_val = st.top(); st.pop();
        }
    }
    
    int top() {
        return st.top();
    }
    
    int getMin() {
        return min_val;
    }
private:
    int min_val;
    stack<int> st;
};

 

All LeetCode Questions List 题目汇总