这是四则或许对你有帮助的讯息

1、👉 最近我发现了一个每日都会推送最新校招资讯的《校招日程》文档，其中包括往届补录、应届实习校招信息,比如各种大厂、国企、银行、事业编等信息都会定期更新，帮忙扩散一下。

2、😍 免费分享阿秀个人学习计算机以来的收集到的免费资源，点此白嫖。

3、🚀如果你想在校招中顺利拿到更好的offer，阿秀建议你多看看前人踩过的坑和留下的经验，事实上你现在遇到的大多数问题你的学长学姐师兄师姐基本都已经遇到过了。

4、🔥 欢迎准备计算机校招的小伙伴加入我的学习圈子，一个人踽踽独行真的不如一群人报团取暖，过去22届和23届的小伙伴好好跟着走下去的，最后基本都拿到了不错的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.

第一版，双栈

执行用时 :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;
};

第二版 ，又一个思路，一次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、注意边界检查，以及最小值的更新

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

执行用时 :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;
};