最小栈问题

问题

实现一个特殊的栈, 在实现栈的基本功能的基础上, 再实现返回栈中最小元素的操作

要求

• pop 、push 、getMin 操作的时间复杂度均为 O(1)
• 可使用现成的栈结构

题解

若使用变量来保存最小值, 在进行多次出入栈操作之后无法保证 getMin() 返回值正确.

使用 minStack 来保存最小值栈, 入栈时若小于 minStack 栈顶元素则压入新元素; 若大于则再压入一个 minStack 栈顶元素.

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

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

    public void push(int newEle) {
        if (minStack.isEmpty()) {
            minStack.push(newEle);
        } else if (newEle < getMin()) {
            minStack.push(newEle);
        } else {
            minStack.push(getMin());
        }

        dataStack.push(newEle);
    }

    public int pop() {
        minStack.pop();
        return dataStack.pop();
    }

    public int top() {
        return dataStack.peek();
    }

    public int getMin() {
        if (minStack.isEmpty()) {
            throw new RuntimeException("Empty stack");
        }
        return minStack.peek();
    }
}

例题: LeetCode #155

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。

• push(x) – 将元素 x 推入栈中。

• pop() – 删除栈顶的元素。

• top() – 获取栈顶元素。

• getMin() – 检索栈中的最小元素。

示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); –> 返回 -3.
minStack.pop();
minStack.top(); –> 返回 0.
minStack.getMin(); –> 返回 -2.

Java

import java.util.Stack;

class MinStack {
    private Stack<Integer> dataStack;
    private Stack<Integer> minStack;
    
    /** initialize your data structure here. */
    public MinStack() {
        dataStack = new Stack<>();
        minStack = new Stack<>();
    }
    
    public void push(int x) {
        if (minStack.isEmpty()) {
            minStack.push(x);
        } else if (x < getMin()) {
            minStack.push(x);
        } else {
            minStack.push(getMin());
        }

        dataStack.push(x);
    }
    
    public void pop() {
        minStack.pop();
        dataStack.pop();
    }
    
    public int top() {
        return dataStack.peek();
    }
    
    public int getMin() {
        if (minStack.isEmpty()) {
            throw new RuntimeException("Empty stack");
        }
        return minStack.peek();
    }
}

Python

class MinStack:
    def __init__(self):
        self.data_stack = []
        self.min_stack = []
        
    def push(self, new_ele):
        if len(self.min_stack) == 0:
            self.min_stack.append(new_ele)
        elif new_ele < self.min_stack[-1]:
            self.min_stack.append(new_ele)
        else:
            self.min_stack.append(self.min_stack[-1])
        
        self.data_stack.append(new_ele)
        
    def pop(self):
        if len(self.data_stack) == 0:
            return None
        self.min_stack.pop()
        self.data_stack.pop()
        
    def top(self):
        return self.data_stack[-1]

    def getMin(self):
        if len(self.min_stack) == 0:
            return None
        return self.min_stack[-1]