题目链接

包含min函数的栈

题目描述

这是一个类实现题。你需要定义一个栈的数据结构，并在其中实现 push, pop, top 函数，以及一个 min 函数。min 函数需要能够在常数时间复杂度 O(1) 内返回栈中的最小元素。

要求实现的方法:

  • push(value): 将 value 压入栈。
  • pop(): 弹出栈顶元素。
  • top(): 获取栈顶元素。
  • min(): 获取栈中当前的最小元素。

约束条件:

  • 题目保证在调用 pop, top, min 时，栈中一定有元素。
  • 所有操作的时间复杂度都应为 O(1)。

解题思路

本题的难点在于设计一个 min 函数，使其时间复杂度为 O(1)。如果只用一个普通的栈，当我们弹出（pop）的元素恰好是当前最小值时，我们就需要遍历整个栈来找到下一个最小值，这会导致 pop 操作的复杂度变为 O(N)，不符合题目要求。

解决这个问题的经典方法是使用一个辅助栈，我们称之为 min_stack，与存储数据的主栈 data_stack 同步操作。

核心设计：

  1. 数据栈 (data_stack): 和普通栈一样，负责存储所有入栈的元素。
  2. 最小栈 (min_stack): 这个栈的栈顶，永远保存着当前 data_stack 中所有元素的最小值。

各函数实现逻辑：

  • push(value):

    1. 将 value 正常压入 data_stack。
    2. 判断 value 和 min_stack 栈顶元素的关系：
      • 如果 min_stack 为空，或者 value 小于或等于 min_stack 的栈顶元素，那么 value 就是新的（或并列的）最小值。此时，也将 value 压入 min_stack。
      • 注意: 必须是"小于或等于"。如果只在小于时压栈，当有重复的最小值（如 5, 2, 2）时，弹出第一个2会导致 min_stack 也弹出2，错误地将最小值更新为5。

  • pop():

    1. 在弹出 data_stack 的栈顶元素之前，先检查这个元素是否等于 min_stack 的栈顶元素。
    2. 如果相等，说明我们正在弹出当前的最小值，那么 min_stack 也必须同步弹出它的栈顶元素，以暴露下一个（即之前的）最小值。
    3. 最后，无论如何都弹出 data_stack 的栈顶元素。

  • top():

    • 直接返回 data_stack 的栈顶元素即可。

  • min():

    • 由于 min_stack 的栈顶始终保存着当前 data_stack 的最小值，所以直接返回 min_stack 的栈顶元素即可。这个操作是 O(1) 的。

通过这种方式，我们用空间换取了时间，使得 push, pop, top, min 所有操作的时间复杂度都达到了 O(1)。

代码

注意：牛客网的这道题要求在一个 Solution 类中实现这些方法，而不是写一个完整的 main 函数。

class Solution {
private:
    stack<int> data_stack;
    stack<int> min_stack;

public:
    void push(int value) {
        data_stack.push(value);
        if (min_stack.empty() || value <= min_stack.top()) {
            min_stack.push(value);
        }
    }
    
    void pop() {
        if (data_stack.top() == min_stack.top()) {
            min_stack.pop();
        }
        data_stack.pop();
    }
    
    int top() {
        return data_stack.top();
    }
    
    int min() {
        return min_stack.top();
    }
};

import java.util.ArrayDeque;
import java.util.Deque;

public class Solution {
    private Deque<Integer> dataStack = new ArrayDeque<>();
    private Deque<Integer> minStack = new ArrayDeque<>();
    
    public void push(int node) {
        dataStack.push(node);
        if (minStack.isEmpty() || node <= minStack.peek()) {
            minStack.push(node);
        }
    }
    
    public void pop() {
        // Integer的==在[-128, 127]之外比较的是对象地址，必须用.equals()
        if (dataStack.peek().equals(minStack.peek())) {
            minStack.pop();
        }
        dataStack.pop();
    }
    
    public int top() {
        return dataStack.peek();
    }
    
    public int min() {
        return minStack.peek();
    }
}

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.data_stack = []
        self.min_stack = []

    def push(self, node):
        self.data_stack.append(node)
        if not self.min_stack or node <= self.min_stack[-1]:
            self.min_stack.append(node)
            
    def pop(self):
        if self.data_stack[-1] == self.min_stack[-1]:
            self.min_stack.pop()
        self.data_stack.pop()
        
    def top(self):
        return self.data_stack[-1]
        
    def min(self):
        return self.min_stack[-1]

算法及复杂度

  • 算法: 双栈/辅助栈。
  • 时间复杂度: 对于 push, pop, top, min 的每一次调用，其时间开销都是常数级别的，即 ，不随栈中元素的数量 N 增长。这是本题解法的核心。如果总共有 K 次操作，那么执行所有操作的总时间复杂度为 。
  • 空间复杂度: 。在最坏的情况下（例如，压入一个单调递减的序列 5, 4, 3, 2, 1），min_stack 的大小会和 data_stack 一样大，其中 N 为压入栈的元素总数。