题目一:
定义栈的数据结构, 请在该类型中实现一个能够得到栈中所含最小元素的 min 函数(时间复杂度应为 O(1)).
时间限制:
1 秒
空间限制:
32768K
解题思路:
首先理解题意, 题目的意思是说要 stack.min()能获取到这个栈的最小元素. 这样的话, 就需要有东西来记录这个最小元素. 但是也不能只记录一个最小值, 因为虽然取完当前的最小值了, 紧接着来了几波 pop()后, 要保证下个 min()是当前剩余的里面最小的.
所以最好的方式就是使用一个辅助栈, 第一个栈就是正常押入, 但是辅助栈中存储的就是压栈中最小的, 一旦再次压入发现比之前的还小, 那么就同时压入辅助栈中. 上个图吧:
可以看出辅助栈中栈顶存放的肯定是目前这个原栈中最小的, 这样不管你 pop()多少, 只要没和辅助栈中的 top()相等, 那么最小值仍然是辅助栈中的 top(). 但是一旦 pop()的相等了, 那就辅助栈中也将栈顶 pop()出. 这样就能保证目前的原栈中的最小值还是在辅助栈中.
class Solution {
stack<int> stack1, stack2;
void push(int value) {
stack1.push(value);
if (stack2.empty()) {
stack2.push(value);
}
else if (value <= stack2.top()) {
stack2.push(value);
}
}
int top() {
return stack1.top();
}
void pop() {
/*注意达到条件也得删2中的值*/
if (stack1.top() == stack2.top()) {
stack2.pop();
}
stack1.pop();
}
int min() {
return stack2.top();
}
}
题目二:
输入两个整数序列, 第一个序列表示栈的压入顺序, 请判断第二个序列是否可能为该栈的弹出顺序. 假设压入栈的所有数字均不相等. 例如序列 1, 2, 3, 4, 5 是某栈的压入顺序, 序列 4, 5, 3, 2, 1 是该压栈序列对应的一个弹出序列, 但 4, 3, 5, 1, 2 就不可能是该压栈序列的弹出序列. (注意: 这两个序列的长度是相等的)
时间限制:
1 秒
空间限制:
32768K
解题思路:
先搞懂题, 起初我的理解是直接将 A 数组全部压入栈, 然后 top()和 pop()结合着看是不是和 B 数组完全一一对应就行了.
只能说思维完全错误, 大脑紊乱. 题目中的例子就是活生生的大脸. 简单来说题目的意思就是有可能在压栈过程中我就出栈, 然后继续压栈. 这样的话, 我们就需要一个辅助容器, vector 和 stack 都行, 我这里使用 vector(在小知识点中分享了几个本题相关的 vector 好用的方法. ). 当从 A 数组中进行压入时, 如果发现和 B 数组的下标所对应的值相等, 那么对辅助栈进行循环 pop, B 数组下标不断向后移动. 旁白: 匹配上了?好让你出一波栈我在压. 当发现不相等的时候, A 中的元素继续向辅助栈中压入, 再与 B 数组当前位置的值进行比较....
class Solution {
public:
bool IsPopOrder(vector<int> pushV,vector<int> popV) {
if (pushVi.empty() || popV.empty()) {
return false;
}
vector<int> tmpStack;
for (int i = 0, j = 0; i < pushV.size(); i++) {
tmpStack.push_back(pushV[i]);
while (tmpStack.back() == popV[j] && j < popV.size()) {
tmpStack.pop_back();
j++;
}
}
return tmpStack.empty();
}
}
小知识点 👍 :
vector
中的常用方法:
push_back
在数组的最后添加一个数据pop_back
去掉数组的最后一个数据back
得到数组的最后一个单元的引用
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于