题解 | 包含min函数的栈

1、解题思路

1. 普通栈：直接使用一个栈来存储所有元素，但 min 操作需要遍历所有元素，时间复杂度为 O(n)，不符合题目要求。
2. 辅助栈：使用一个辅助栈来同步存储当前栈中的最小值。每次 push 操作时，辅助栈压入当前最小值；每次 pop 操作时，辅助栈同步弹出。这样 min 操作只需返回辅助栈的栈顶元素即可。

2、代码实现

C++

#include <stack>
class Solution {
  public:
    void push(int value) {
        dataStack.push(value);  // 压入主栈
        // 压入辅助栈: 如果辅助栈为空或者新值 <= 当前最小值, 则压入新值
        if (minStack.empty() || value <= minStack.top()) {
            minStack.push(value);
        } else {
            // 否则重复压入当前最小值
            minStack.push(minStack.top());
        }
    }
    void pop() {
        if (!dataStack.empty()) {
            dataStack.pop();    // 弹出主栈
            minStack.pop(); // 同步弹出辅助栈
        }
    }
    int top() {
        return dataStack.top(); // 直接返回主栈栈顶
    }
    int min() {
        return minStack.top();  // 直接返回辅助栈栈顶元素 (当前最小值)
    }

  private:
    stack<int> dataStack;   // 主栈存储所有元素
    stack<int> minStack;    // 辅助栈同步存储当前最小值
};

Java

import java.util.*;
import java.util.Stack;

public class Solution {
    private Stack<Integer> dataStack = new Stack<>();
    private Stack<Integer> minStack = new Stack<>();

    public void push(int node) {
        dataStack.push(node); // 压入主栈
        // 压入辅助栈：如果辅助栈为空或者新值 <= 当前最小值，则压入新值
        if (minStack.isEmpty() || node <= minStack.peek()) {
            minStack.push(node);
        } else {
            // 否则重复压入当前最小值
            minStack.push(minStack.peek());
        }
    }

    public void pop() {
        if (!dataStack.isEmpty()) {
            dataStack.pop(); // 弹出主栈
            minStack.pop();  // 同步弹出辅助栈
        }
    }

    public int top() {
        return dataStack.peek(); // 直接返回主栈顶元素
    }

    public int min() {
        return minStack.peek(); // 直接返回辅助栈顶元素（当前最小值）
    }
}

Python

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.data_stack = []  # 主栈存储所有元素
        self.min_stack = []   # 辅助栈同步存储当前最小值

    def push(self, node):
        # write code here
        self.data_stack.append(node)  # 压入主栈
        # 压入辅助栈：如果辅助栈为空或者新值 <= 当前最小值，则压入新值
        if not self.min_stack or node <= self.min_stack[-1]:
            self.min_stack.append(node)
        else:
            # 否则重复压入当前最小值
            self.min_stack.append(self.min_stack[-1])

    def pop(self):
        # write code here
        if self.data_stack:
            self.data_stack.pop()  # 弹出主栈
            self.min_stack.pop()   # 同步弹出辅助栈


    def top(self):
        # write code here
        return self.data_stack[-1]  # 直接返回主栈顶元素

    def min(self):
        # write code here
        return self.min_stack[-1]   # 直接返回辅助栈顶元素（当前最小值）

3、复杂度分析

1. 时间复杂度 ： push、pop、top、min 均为 O(1)。
2. 空间复杂度：O(n)，辅助栈额外存储 n 个元素。