【面试经典150 | 栈】最小栈

Tag

【设计类】【栈】

---

题目来源

155. 最小栈

---

题目解读

本题是一个设计类的题目，设计一个最小栈类 MinStack() 实现：

• MinStack()：初始化堆栈对象；
• void push(int val)：将元素val推入堆栈；
• void pop()：删除堆栈顶部的元素；
• int top()：获取堆栈顶部的元素；
• int getMin()：获取堆栈中的最小元素。

---

解题思路

方法一：辅助栈

维护两个栈，一个栈就是常规的栈 stk1，另一个栈 stk2 用来存放已经插入栈 stk1 中数字的最小值。

注意入栈和出栈操作时两个栈都要更新。

实现代码

class MinStack {
	
public:
	MinStack() {
		min_stk.push(INT_MAX);
	}

	void push(int val) {
		stk.push(val);
		min_stk.push(std::min(min_stk.top(), val));
	}

	void pop() {
		stk.pop();
		min_stk.pop();
	}

	int top() {
		return stk.top();
	}

	int getMin() {
		return min_stk.top();
	}

private:
	std::stack<int> stk;
	std::stack<int> min_stk;
};

/**
 * 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();
 */
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

复杂度分析

时间复杂度：$O(1)$。

空间复杂度：$O(n)$，$n$ 为 操作次数。

方法二：一个栈

可以只使用一个栈来同时保存当前的最小值和 val。

实现代码

class MinStack {
private:
    stack<pair<int, int>> stk;
public:
    MinStack() {
        stk.push(make_pair(INT_MAX, INT_MAX));
    }
    
    void push(int val) {
        stk.push({min(stk.top().first, val), val});
    }
    
    void pop() {
        stk.pop();
    }
    
    int top() {
        return stk.top().second;
    }
    
    int getMin() {
        return stk.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();
 */
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

复杂度分析

时间复杂度：$O(1)$。

空间复杂度：$O(1)$。

方法三：栈中存放差值

现在我们维护一个变量 minVal，表示当前插入的变量的最小值，栈中每次入栈的是 val 与 minVal 的差值 differ。现在进行具体分析：

• push(int val)：如果此时栈为空，我们更新 minVal = val，向栈中插入 0；如果此时栈非空，首先向栈中插入 diff，根据 diff 的值来更新 minVal：
  • 如果 diff > 0，说明插入的 val 大于当前的 minVal，则 minVal 不需要更新；
  • 否则表明插入的 val 小于或者等于当前的 minVal，则更新 minVal = val。
• pop()：我们需要根据 diff 来更新弹出栈顶元素后的 minVal，具体地：
  • 先弹出栈顶元素 diff，并 pop；
  • 如果 diff > 0，说明我们当时插入的 val 大于当时的 minVal，则 minVal 是不需要更新的；
  • 否则说明当时插入的 val 小于或者等于 minVal，当时的 minVal 是插入的 val，需要将 minVal 还原回去，即当时插入 val 更新 minVal 的过程如下，还原回去得到 minVal = minVal + diff。

$$diff=val-minVal;minVal=val;$$

• top()：如果 diff < 0，表示 minVal 就是最小栈的栈顶元素，否则 minVal + diff 才是最小栈的栈顶元素。
• getMin()：直接返回 minVal 即可。

实现代码

class MinStack {
private:
    stack<long long> stk;
    long long minVal, diff;
public:
    MinStack() {
    }
    
    void push(int val) {
        if (stk.empty()) {
            stk.push(0);
            minVal = val;
        }
        else {
            diff = val - minVal;
            stk.push(diff);
            minVal = diff > 0 ? minVal : val;
        }
    }
    
    void pop() {
        diff = stk.top();
        stk.pop();
        if (diff < 0) {
            minVal = minVal - diff;
        }
    }
    
    int top() {
        return stk.top() < 0 ? minVal : minVal + stk.top();
    }
    
    int getMin() {
        return minVal;
    }
};

/**
 * 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();
 */
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

复杂度分析

时间复杂度：$O(1)$。

空间复杂度：$O(1)$。

---

其他语言

python3

以下只给出方法三的 python3 代码，该方法比较巧妙，值得好好研究。

class MinStack:
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []

    def push(self, x: int) -> None:
        if not self.stack:
            self.stack.append(0)
            self.min_value = x
        else:
            diff = x-self.min_value
            self.stack.append(diff)
            self.min_value = self.min_value if diff > 0 else x

    def pop(self) -> None:
        if self.stack:
            diff = self.stack.pop()
            if diff < 0:
                self.min_value = self.min_value - diff

    def top(self) -> int:
        return self.min_value if self.stack[-1] < 0 else self.stack[-1] + self.min_value

    def getMin(self) -> int:
        return self.min_value if self.stack else -1
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

---

写在最后

如果文章内容有任何错误或者您对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度方法，欢迎评论区交流。

最后，感谢您的阅读，如果感到有所收获的话可以给博主点一个 👍 哦。