先来看第一道题——:最小栈
题目要求我们设计一个
MinStack
类:
除了提供常见的几个接口之外,还要搞一个int getMin()
,使得我们能够在常数时间O(1)内获取到栈中最小的元素。
那要怎么做呢?
大家想这样行不行: 我们定义一个变量min来保存最小值,向栈里面入第一个元素时,就让min等于第一个元素,后续入栈新元素时,就和min比较判断是否需要更新min,小于就更新,大于就不动。 最终min的值就是最小元素。 听起来好像可以,但是: 别忘了,元素可以入栈,也可以出栈啊
比如现在栈里面入了这样几个元素,现在min的值更新为1,确实是当前栈中所有元素的最小值。 但是如果我们进行了pop呢? 如果先把8pop掉了:
此时min的值还是1没问题,那继续pop呢?
1也被pop掉了,那min还能等于1 吗? 所以这样不行。
那我们提供这样一种思路:
我们这样做: 实现的
MinStack
类里有两个成员:
st
就是我们正常定义的要使用的栈,min_st
是一个辅助栈,用来帮助我们获取最小值。
那对于这两个栈,我们怎么操作呢?
举个栗子: 当第一个元素入栈的时候,比如入了一个5,那我们让两个栈都push一个5:
那此时栈中的最小值就是5。
然后再入一个4,最小值要更新,那min_st
和st
都push一个4(其实就是保证min_st栈顶的元素一定是最小值,最终我们就可以直接获取):
然后如果再入一个6,那最小值不需要更新:
那min_st要push入元素吗? 🆗,可以入也可以不入,但入得话一定不入6,因为入6的话栈顶元素就不是最小值了,所以如果选择入的话再入一个4:
那这样min_st栈顶的元素还是最小的。 再入的话一样的操作:
那我们在这里选择不入:
那就是这样:
当入栈的新元素小于等于min_st.top()
(或第一次min_st
为空)时 min_st
才入栈这个元素。
那pop的时候怎么处理?
🆗,是不是pop的元素等于当前栈中的最小值即
min_st.top()
,min_st
才进行pop,否则min_st
就不pop。
我们来写一下代码:
这是题目的初始代码模板。
首先问大家一个问题:
这是我们的成员变量嘛。 我们看到题目给的代码模板里面给了构造函数的接口:
但是,对于我们这种方法,还需要些构造函数吗? 其实是不是根本都不需要构造函数啊,因为我们不写编译器默认生成,默认生成的构造函数什么特性: 编译器自动生成的构造函数不会对内置类型成员进行处理,而对于我们这里的stack(自定义类型)会怎么处理? 是不是会去调用stack对应的默认构造函数。 所以这里完全不需要构造函数,另外对于什么拷贝构造、赋值重载是不是一样啊。 但是呢这里给了构造函数的接口,那编译器就不会默认生成了,那如果我们对于这个构造函数啥也不写,就留在这里,会不会出问题? 🆗,是不是也没问题啊,因为它会走初始化列表,对于自定义类型也会去调它的默认构造
那剩下的接口就很好实现了,我们上面已经分析过了,这里就直接上代码了:
class MinStack {
public:
// 不需要处理走初始化列表就可以搞定,
// 直接删掉也可以,因为默认生成的就可以搞定
MinStack() {
}
void push(int val) {
st.push(val);
if(min_st.empty()||val<=min_st.top())
min_st.push(val);
}
void pop() {
if(st.top()==min_st.top())
min_st.pop();
st.pop();
}
int top() {
return st.top();
}
int getMin() {
return min_st.top();
}
private:
stack<int> st;
stack<int> min_st;
};
可以给大家看一下,直接删掉构造也可以:
现在给大家一个问题,还是上面那道题目:
如果是这种情况,那st有多少元素,minst也得有多少元素。 那能不能想个办法优化一下呢? 🆗,我们可以考虑这样做: 我们的minst里面呢不在存最小值,而去存它的值和个数:
这样需要minst进行pop的话,把对应的个数- -就行了,怎么存个数呢,可以定义一个结构体:
那这样如果重复值比较多的话,可以节省一点空间。 就是这样一个思路,那代码我就不写了,大家有兴趣可以尝试写一下。
链接: link
这道题其实就是给我们一个入栈序列,和一个出栈序列,让我们判断该出栈序列是否是可行的。
那怎么判断呢?
🆗,这道题比较简单的一种方法其实就是去模拟这个入栈出栈的过程。 举个栗子,就看题目给的这个测试用例:
入栈序列是1 2 3 4 5,出栈顺序是4 3 5 1 2。 那我们就模拟这个过程去判断啊: 首先上来第一步肯定先入一个数据,根据入栈序列第一个入栈的是1,那1入完之后有没有可能直接出栈啊,当然是有可能的,不过我们要看对应的出栈序列,那我们看到第一个出栈的应该是4,所以怎么办?
我们需要继续入栈数据,接着入栈2 3 4。
这是栈顶的元素和出栈序列第一个元素相等,所以出栈,4,3都顺利的出了
下一个要出栈的是5,但是5还没入栈,所以让5入栈,然后5直接出栈
然后现在栈里只剩1 2了,但是出栈序列是1 2,这显然不能办到,所以应该返回false
(最终栈不为空)
当然如果是4 3 5 2 1,这样最终2 1也能顺利出栈,那就应该是true
(最终栈为空)
那对应的代码怎么写呢,我们来一起写一下:
给了我们两个vector,存储入栈pushV
和出栈popV
的序列。
那我们要模拟入栈出栈的过程,所以我们定义一个栈
然后我们要根据入栈序列去push数据,根据出栈序列去pop数据,所以我们要去遍历两个vector。
从下标0开始。 首先上来第一步肯定先入一个数据:
然后pushi++,下一次入第二个数据。
那第一个元素入了之后我们就要判断它是否需要出栈了,怎么判断?
如果当前入栈的元素等于popV[popi]
,是不是就要出栈。
但是每次出栈是不是有可能连续出多个元素啊,所以这应该是一个循环:
但是,我们这里上来直接获取栈顶元素去判断st.top()==popV[popi]
,如果栈空了再去st.top()是不是就出问题了啊,所以,循环结束的条件是不相等或者栈出空了:
内层while循环结束之后如果后面还有元素未入栈,那就继续入栈,继续判断,当外层while循环结束是不是所有数据都判断完了啊。 那此时如果栈为空是不是就表明出栈序列是匹配的,全部出完了,如果不为空,就证明不匹配:
就写完了。
class Solution {
public:
bool IsPopOrder(vector<int> pushV,vector<int> popV) {
stack<int> st;
int pushi=0;
int popi=0;
while(pushi<pushV.size())
{
st.push(pushV[pushi++]);
while(!st.empty()&&st.top()==popV[popi])
{
st.pop();
popi++;
}
}
return st.empty();
}
};
链接: link
这道题目叫做逆波兰表达式求值,那什么是逆波兰表达式呢? 我们可以一起来了解一下:
结合题目中给的测试用例给大家解释一下:
我们正常写的表达式,就比如题目中的这个:(2 + 1) * 3
这种写法叫做中缀算术表达式,即运算符写在操作数的中间,但是这种写法计算机是不能直接计算的,因为涉及运算符优先级的问题,比如1+2*3
,应该先算*
。
所以呢,这里就需要我们做一件事情,就是把它变成后缀表达式,其实就是根据优先级对表达式中的运算符排一个序,并且放到对应的操作数后面。
就比如题目中给的这个示例:((2 + 1) * 3)
这个表达式对应的后缀表达式就是["2","1","+","3","*"]
(题中是把它放到一个字符串数组中了)。
即1和2先进行后面的+,得到的结果再和3进行后面的*,得到最终结果。这样就直接从前往后算,不用考虑优先级的问题了。
那现在大家对逆波兰表达式应该有一个大致的了解了。
但是呢,单要解这道题目的话,其实很好搞:
我们只需要借助一个栈就搞定了。 具体怎么做呢? 我们去遍历给的逆波兰表达式对应的字符串数组,如果对应的元素是数字,我们就让该操作数入栈,如果遇到操作符,我们就去取栈顶的前两个元素(并pop掉)进行对应的运算,然后将结果入栈,后续重复上述操作,最终栈里面唯一的那个元素就是要求的结果。 举个栗子:
遍历tokens,2 1入栈,接着遇到+,取出 1 2相加,得到结果3入栈,后面又是一个3入栈,接着遇到* ,取出3 3相乘,结果9入栈。 最终栈里面唯一的元素9就是结果。
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> st;
for(auto& str:tokens)
{
if(str=="+"||str=="-"||str=="*"||str=="/")
{
int right=st.top();
st.pop();
int left=st.top();
st.pop();
switch(str[0])
{
case '+':
st.push(left+right);
break;
case '-':
st.push(left-right);
break;
case '*':
st.push(left*right);
break;
case '/':
st.push(left/right);
break;
}
}
else
{
st.push(stoi(str));
}
}
return st.top();
}
};
那现在大家再来思考一个问题: 如果给我们一个中缀表达式,我们如何把它转换成对应的后缀表达式?
那中缀转后缀呢,也是需要借助一个栈,具体怎么做呢? 比如现在有这样一个中缀表达式
1+2*3-4
怎么把它转成后缀呢? 🆗,我们还是从头去遍历这个表达式,如果遇到的是操作数,就输出;
如果遇到的是的是操作符,那这时要分情况进行分析: 如果此时栈为空,就让该操作符进栈;
如果遇到的是操作符,且此时栈不为空,则取栈顶的操作符与当前操作符比较,比较啥呢——优先级: 如果比栈顶操作符优先级高,就让该操作符进栈,为什么是进栈而不是拿它进行运算呢? 因为后面有可能还有优先级更高的,所以先进栈。
那进栈之后呢?继续取下一个进行判断是操作数还是操作符。
如果比栈顶操作符优先级低或者相等,则出栈顶的操作符输出(即此时栈顶的这个操作符可以进行运算了)
然后再去判断栈是否为空,不为空再拿当前操作符和栈顶操作符比较,进行相应操作,为空就入栈。
遍历结束后,如果栈不为空,将剩余操作符输出。
此时,就得到对应的后缀表达式了。
但是,如果是带括号的情况呢?
比如
1+2*(4-5)+6/7
,怎么处理? 🆗,那如果按照上面的分析,1输出,+
入栈,2输出,*
的优先级比栈顶的+高,*
也入栈,接着遇到了括号,怎么办?
如果不加括号的话,后面-比*
优先级低,那应该让*
先出栈运算,但是现在-在括号里面,所以-应该先运算,所以要认为-的优先级更高。
那我们可以怎么处理呢?当然这里的方法可能不止一种,我们可以这样做:
遇到(
,我们认为它的优先级很低,但是我们不拿(
做比较,直接让它入栈
然后遇到括号里的-
,栈不为空,比较,因为我们说了认为(
的优先级很低,所以-也入栈
那继续往后走遇到)
怎么办?
🆗,)
呢我们也认为它的优先级很低,但是)
我们要拿它去比较,因为我们认为)
优先级很低,所以此时栈顶的-
是不是就被成功弹出了。
然后栈不为空继续跟栈顶比,那此时)
就遇到 (
了,拿这时怎么做呢?
这时直接把(
pop掉,不输出,然后跳过)
继续看下一个,因为后缀表达式优先级都排好了就不需要括号了。
拿继续往后走遇到+
,栈不为空,跟栈顶比,比栈顶优先级低,栈顶操作符*
输出,继续栈还不为空,继续比,优先级相等,出栈顶操作符+
然后栈空了,+
入栈
然后遇到6入栈,遇到/
优先级比+
高,入栈,然后7输出
就遍历完了,再把剩余操作符输出
就得出结果后缀表达式了,大家可以验证一下。
当然处理括号可能有很多种方法,我们这里提供的只是其中一种,而且我们这种方法如果遇到有些极端的情况可能也不一定处理的了,可能还需要加一些特殊处理。
另外我们会发现就是遇到(
是不是好像去开了一个新栈,在这个新栈里去处理括号里的这个子表达式,所以如果这样的问题也可以考虑递归去搞,每次遇到(
就递归去处理这个子表达式,处理完回去递归调用的地方继续处理后面的。
这个问题大家了解一下。