时间轴

2025-11-18

init

题目：

P155 最小栈

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

最小堆+ 懒删除

这是我最先想出的方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#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 不记录值，而是记录与最小值的偏移量，用另外一个数存放最小值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#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 = 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();
 */