面试经典150题 P155 最小栈

---

时间轴

2025-11-18

init

---

题目：

P155 最小栈

https://leetcode.cn/problems/min-stack/description/?envType=study-plan-v2&envId=top-interview-150

最小堆+ 懒删除

这是我最先想出的方法：

#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <unordered_set>

using std::priority_queue;
using std::vector;
using std::stack;
using std::pair;
using std::unordered_set;

class MinStack {
    private:
	// {value, index}
	priority_queue<pair<int, int>, vector<pair<int, int> >, std::greater<pair<int, int> > > min_heap;
	unordered_set<int> lazy_deleted;

	// {value, index}
	stack<pair<int, int> > st;

	int idx;

    public:
	MinStack()
	{
		idx = 0;
	}

	void push(int val)
	{
		int curr_id = idx++;
		min_heap.push({ val, curr_id });
		st.push({ val, curr_id });
	}

	void pop()
	{
		int index = st.top().second;

		st.pop();

		if (min_heap.top().second == index) {
			min_heap.pop();
		} else {
			lazy_deleted.insert(index);
		}
	}

	int top()
	{
		return st.top().first;
	}

	int getMin()
	{
		while (lazy_deleted.count(min_heap.top().second)) {
			min_heap.pop();
		}
		return min_heap.top().first;
	}
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

O(1)额外空间

stack 不记录值，而是记录与最小值的偏移量，用另外一个数存放最小值

#include <stack>
using std::stack;

class MinStack {
    private:
	// 记录与最小值的偏移
	stack<long> st;
	long min_val;

    public:
	MinStack()
	{
	}

	void push(int val)
	{
		if (st.empty()) {
			st.push(0);
			min_val = val;
		} else {
			long diff = val - min_val;
			st.push(diff);

			if (diff < 0) // 当前栈顶值小于min_val，更新最小值
				min_val = val;
		}
	}

	void pop()
	{
		long diff = st.top();
		st.pop();

		if (diff < 0)
			min_val = min_val - diff; // 恢复上一个最小值
	}

	int top()
	{
		long offset = st.top();
		if (offset <= 0) // 说明当前栈顶刚好就是最小值
			return (int)min_val;
		else
			return (int)(min_val + offset);
	}

	int getMin()
	{
		return (int)min_val;
	}
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

leetcode hot 100 rewrite, 虽然花了点时间还是自己写出来了，总结两个易错的点：

1. 要用 long 而不是 int, 因为 -2^31 <= val <= 2^31 - 1
2. 当前栈顶为负数时，此时 top() 应该返回 min_val

#include <stack>
using std::stack;

// -2^31 <= val <= 2^31 - 1

class MinStack {
    private:
        stack<long> stk; // 保存与最小值的差值
        long min_val;

    public:
        MinStack()
        {
        }

        void push(int val)
        {
                // 3 2 4 6 1
                // val = 3, push 0, stack[0], min_val == 3

                // val = 2, push 2 - 3 = -1, stack[0, -1], min_val = 2
                // val = 4, push 4 - 2 =  2, stack[0, -1, 2], min_val = 2
                // val = 6, push 6 - 2 =  4, stack[0, -1, 2, 4], min_val = 2
                // val = 1, push 1 - 2 = -1, stack[0, -1, 2, 4, -1], min_val = 1

                long input_val = (long)val;

                if (stk.empty()) {
                        min_val = input_val;
                        stk.push(0);
                        return;
                }

                stk.push(input_val - min_val);

                if (val < min_val)
                        min_val = input_val;
        }
        // pop、top 和 getMin 操作总是在 非空栈 上调用
        void pop()
        {
                long top_val = stk.top();

                if (top_val < 0)
                        min_val = min_val - top_val;

                stk.pop();
        }

        int top()
        {
                long top_val = stk.top();

                if (top_val > 0)
                        return (int)(top_val + min_val);
                else
                        return min_val;
        }

        int getMin()
        {
                return (int)min_val;
        }
};