如果你想在校招中顺利拿到更好的offer,阿秀建议你多看看前人的经验 ,比如准备简历实习上岸经历校招总结阿里、字节、腾讯、美团等一二线大厂真实面经也欢迎来一起参加秋招打卡活动 等;如果你是计算机小白,学习/转行/校招路上感到迷茫或者需要帮助,可以点此联系阿秀;免费分享阿秀个人学习计算机以来的收集到的好资源,点此白嫖;如果你需要《阿秀的学习笔记》网站中求职相关知识点的PDF版本的话,可以点此下载

# 155. 最小栈

力扣原题链接(点我直达) (opens new window)

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

  • push(x) -- 将元素 x 推入栈中。
  • pop() -- 删除栈顶的元素。
  • top() -- 获取栈顶元素。
  • getMin() -- 检索栈中的最小元素。

示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.
1
2
3
4
5
6
7
8

# 第一版,双栈

执行用时 :64 ms, 在所有 C++ 提交中击败了37.18%的用户

内存消耗 :16.8 MB, 在所有 C++ 提交中击败了77.33%的用户

class MinStack {
public:
	/** Initialize your data structure here. */
	MinStack() {

	}

	/** Push element x to the back of queue. */
	void push(int x) {

		stVal.push(x);
		if (stMin.empty() || x < stMin.top()) //双栈,同步保存当前最小值,如果是第一个x或者小于当前最小值,就把新的最小值存储进来
			stMin.push(x);
		else
			stMin.push(stMin.top());
	}

	/** Removes the element from in front of queue and returns that element. */
	void pop() {

		stMin.pop();
		stVal.pop();
	}

	/** Get the front element. */
	int top() {

		return stVal.top();
	}

	/** Returns whether the queue is empty. */
	int getMin() {
		return stMin.top();
	}

private:
	stack<int> stVal, stMin;
};
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

# 第二版 ,又一个思路,一次push两个进去

每次push时,第一次push进x,第二次push当前的最小值

执行用时 :64 ms, 在所有 C++ 提交中击败了37.18%的用户

内存消耗 :16.7 MB, 在所有 C++ 提交中击败了93.90%的用户

class MinStack {
public:
	/** Initialize your data structure here. */
	MinStack() {
	}

	/** Push element x to the back of queue. */
	void push(int x) {
		if (st.empty()) {
			numMin = x;
			st.push(x);
			st.push(x);
		}
		else
		{
			numMin = min(numMin, x);
			st.push(x);
			st.push(numMin);
		}

	}

	/** Removes the element from in front of queue and returns that element. */
	void pop() {
		st.pop();
		st.pop();
		if(!st.empty()) //注意可能会有st为空的情况,直接写numMin=st.top()会报错,要注意更新最小值
			numMin = st.top();
	}

	/** Get the front element. */
	int top() {
		int numMinTemp = st.top();//先保存最后的小的值
		st.pop();
		numTemp = st.top();
		st.push(numMinTemp);
		return numTemp; //不能返回局部变量的值以及地址
	}

	/** Returns whether the queue is empty. */
	int getMin() {
		return st.top();
	}

private:
	stack<int> st = {};
	int numMin, numTemp;
};
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

几个教训:

1、函数返回时,不能返回局部变量的值以及地址

2、注意边界检查,以及最小值的更新

# 第三版 第二版的变形,但是快很多了

执行用时 :36 ms, 在所有 C++ 提交中击败了90.66%的用户

内存消耗 :17 MB, 在所有 C++ 提交中击败了36.11%的用户

先输入最小值,再push当前值,这样get_top(),会快一点

class MinStack {
public:
	/** Initialize your data structure here. */
	MinStack() {

	}

	/** Push element x to the back of queue. */
	void push(int x) {
		if (st.empty()) {
			numMin = x;
			st.push(x);
			st.push(x);
		}
		else
		{

			numMin = min(numMin, x);
			st.push(numMin);
			st.push(x);
		}

	}

	/** Removes the element from in front of queue and returns that element. */
	void pop() {
		st.pop();
		st.pop();
		if (!st.empty())
		{
			int numTemp = st.top();
			st.pop();
			numMin = st.top();
			st.push(numTemp);
		}
	}

	/** Get the front element. */
	int top() {

		return st.top();
	}

	/** Returns whether the queue is empty. */
	int getMin() {
		int numTempT = st.top();
		st.pop();
		numTemp = st.top();
		st.push(numTempT);
		return numTemp;
	}

private:
	stack<int> st = {};
	int numMin, numTemp;
};
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