最小栈

题解思路

这道题要求实现一个栈（Stack），并在常数时间内（$O(1)$）获取栈中的最小值。由于栈的基本操作（push、pop、top）都是 $O(1)$ 的，我们的目标是保证 getMin 也能达到 $O(1)$ 的复杂度。

方法：辅助栈

思路：
我们使用两个栈：

• 数据栈（data_stack）：用于存储所有的入栈元素。
• 最小值栈（min_stack）：用于存储当前栈中最小的元素。

每次 push(x) 时：

1. 将 x 压入 data_stack。
2. 如果 min_stack 为空或者 x 小于等于 min_stack 的栈顶元素，则将 x 也压入 min_stack，保证 min_stack 的栈顶始终是当前最小值。

每次 pop() 时：

1. 先从 data_stack 弹出元素。
2. 如果该元素等于 min_stack 的栈顶元素，则同步弹出 min_stack 的栈顶，确保 min_stack 维护的是当前最小值。

top() 直接返回 data_stack 的栈顶元素。
getMin() 直接返回 min_stack 的栈顶元素，时间复杂度 $O(1)$。

复杂度分析

• 入栈操作 push(x)：$O(1)$
• 出栈操作 pop()：$O(1)$
• 获取栈顶 top()：$O(1)$
• 获取最小值 getMin()：$O(1)$

使用了一个额外的栈来存储最小值，因此 空间复杂度 为 $O(n)$。

代码实现

Python 代码

class Solution:
    class MinStack:
        def __init__(self):
            """ 初始化栈和辅助栈 """
            self.data_stack = []  # 数据栈
            self.min_stack = []   # 维护最小值的辅助栈

        def push(self, val: int):
            """ 将元素压入栈 """
            self.data_stack.append(val)
            # 只有当最小栈为空或新元素不大于最小栈的栈顶时，才推入最小栈
            if not self.min_stack or val <= self.min_stack[-1]:
                self.min_stack.append(val)

        def pop(self):
            """ 弹出栈顶元素 """
            if self.data_stack:
                top_element = self.data_stack.pop()
                if top_element == self.min_stack[-1]:  # 同步弹出最小栈的栈顶
                    self.min_stack.pop()

        def top(self) -> int:
            """ 返回栈顶元素 """
            return self.data_stack[-1] if self.data_stack else None

        def getMin(self) -> int:
            """ 返回栈中最小元素 """
            return self.min_stack[-1] if self.min_stack else None


if __name__ == "__main__":
    import sys
    input = sys.stdin.read
    data = input().split("\n")
    
    n = int(data[0])
    stack = Solution.MinStack()
    
    results = []
    for i in range(1, n + 1):
        command = data[i].split()
        if command[0] == "push":
            stack.push(int(command[1]))
        elif command[0] == "pop":
            stack.pop()
        elif command[0] == "top":
            results.append(str(stack.top()))
        elif command[0] == "getMin":
            results.append(str(stack.getMin()))
    
    print("\n".join(results))

Java 代码

import java.util.Scanner;
import java.util.Stack;

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

            /** 初始化栈 */
            public MinStack() {
                dataStack = new Stack<>();
                minStack = new Stack<>();
            }

            /** 压入元素 */
            public void push(int val) {
                dataStack.push(val);
                if (minStack.isEmpty() || val <= minStack.peek()) {
                    minStack.push(val);
                }
            }

            /** 弹出栈顶元素 */
            public void pop() {
                if (!dataStack.isEmpty()) {
                    int topElement = dataStack.pop();
                    if (topElement == minStack.peek()) {
                        minStack.pop();
                    }
                }
            }

            /** 获取栈顶元素 */
            public int top() {
                return dataStack.peek();
            }

            /** 获取最小元素 */
            public int getMin() {
                return minStack.peek();
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = Integer.parseInt(scanner.nextLine());
        Main main = new Main();
        Solution solution = main.new Solution();
        Solution.MinStack stack = solution.new MinStack();
        
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            String[] command = scanner.nextLine().split(" ");
            if (command[0].equals("push")) {
                stack.push(Integer.parseInt(command[1]));
            } else if (command[0].equals("pop")) {
                stack.pop();
            } else if (command[0].equals("top")) {
                sb.append(stack.top()).append("\n");
            } else if (command[0].equals("getMin")) {
                sb.append(stack.getMin()).append("\n");
            }
        }
        System.out.print(sb.toString());
    }
}

C++ 代码

#include <iostream>
#include <stack>
#include <string>

using namespace std;

class Solution {
public:
    class MinStack {
    private:
        stack<int> dataStack;
        stack<int> minStack;
    public:
        /** 初始化栈 */
        MinStack() {}

        /** 压入元素 */
        void push(int val) {
            dataStack.push(val);
            if (minStack.empty() || val <= minStack.top()) {
                minStack.push(val);
            }
        }

        /** 弹出栈顶元素 */
        void pop() {
            if (!dataStack.empty()) {
                if (dataStack.top() == minStack.top()) {
                    minStack.pop();
                }
                dataStack.pop();
            }
        }

        /** 获取栈顶元素 */
        int top() {
            return dataStack.top();
        }

        /** 获取最小元素 */
        int getMin() {
            return minStack.top();
        }
    };
};

int main() {
    int n;
    cin >> n;
    cin.ignore(); 

    Solution::MinStack stack;
    string command;
    while (n--) {
        getline(cin, command);
        if (command.substr(0, 4) == "push") {
            int val = stoi(command.substr(5));
            stack.push(val);
        } else if (command == "pop") {
            stack.pop();
        } else if (command == "top") {
            cout << stack.top() << endl;
        } else if (command == "getMin") {
            cout << stack.getMin() << endl;
        }
    }
    return 0;
}

题目内容

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

实现 $MinStack$ 类:

• $MinStack()$ 初始化堆栈对象。

• $void push(int val)$ 将元素val推入堆栈。

• $void pop()$ 删除堆栈顶部的元素。

• $int top()$ 获取堆栈顶部的元素。

• $int getMin()$ 获取堆栈中的最小元素。

输入描述

输入包含多行：

• 第一行是一个整数 n，表示操作次数
• 接下来的 n 行，每行包含一个操作：
  • "push x" (x 是整数)：将 x 推入栈
  • "pop"：弹出栈顶元素
  • "top"：获取栈顶元素
  • "getMin"：获取栈中最小元素

输出描述

对于每个 "top" 和 "getMin" 操作，输出对应的结果（每行一个整数）。其他操作无需输出。

样例1

输入

7
push -2
push 0
push -3
getMin
pop
top
getMin

输出

-3
0
-2

说明

• MinStack minStack = new MinStack();
• minStack.push(-2); // 栈：[-2]
• minStack.push(0); // 栈：[-2, 0]
• minStack.push(-3); // 栈：[-2, 0, -3]
• minStack.getMin(); // 返回 -3
• minStack.pop(); // 栈：[-2, 0]
• minStack.top(); // 返回 0
• minStack.getMin(); // 返回 -2

提示

• $-2^{31} <= val <= 2^{31} - 1$
• $pop$、$top$ 和 $getMin$操作总是在非空栈上调用
• $push$, $pop$, $top$, $and\ getMin$最多被调用 $3 * 10^4$ 次