Top Interview 150 P155 Min Stack

---

Timeline

Timeline

2025-11-18

init

Stack

---

Problem:

P155 Min Stack

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

Min heap + lazy deletion

This is the first method I thought of:

#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) extra space

The stack does not store the value; instead it stores the offset from the minimum value, and uses another variable to store the minimum value.

#include <stack>
using std::stack;

class MinStack {
    private:
	// Record the offset from the minimum value
	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) // When the current stack top value is less than min_val, update the minimum value.
				min_val = val;
		}
	}

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

		if (diff < 0)
			min_val = min_val - diff; // Restore the previous minimum value
	}

	int top()
	{
		long offset = st.top();
		if (offset <= 0) // It means the current stack top is exactly the minimum value.
			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. Although it took some time, I managed to write it myself. Let me summarize two error-prone points:

1. Use long instead of int, because-2^31 <= val <= 2^31 - 1
2. When the current stack top is negative, top() should return min_val at this point.

#include <stack>
using std::stack;

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

class MinStack {
    private:
        stack<long> stk; // Store the difference from the minimum value
        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, and getMin operations are always called on a non-empty stack.
        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;
        }
};