描述
输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。
1. 0<=pushV.length == popV.length <=1000
2. -1000<=pushV[i]<=1000
3. pushV 的所有数字均不相同
输入:
[1,2,3,4,5],[4,5,3,2,1]
返回值:
true
说明:
可以通过push(1)=>push(2)=>push(3)=>push(4)=>pop()=>push(5)=>pop()=>pop()=>pop()=>pop() 这样的顺序得到[4,5,3,2,1]这个序列,返回true
解读
栈的问题一般是考察性质。因此想要验证popV是否满足合适的pop顺序,只需要模拟实现一下栈的先进后出即可。因此我们需要额外借助一个栈,来进行入栈,出栈操作。
出栈时,需要比较()和popV[i]是否一致。
操作时,让入栈序列先入栈,然后让栈顶数据和出栈数据比较。
当结束时,如果栈全部出完,则为true,否则为false
代码
分为两层循环:
外循环:将数据不断入栈
内循环:匹配数据,匹配成功则出数据
写循环条件的时候,想好是继续的条件还是结束的条件。
结束条件:
当数据全部入栈则循环结束。
当结束之后栈为空,则为true;否则为false
class Solution {
public:
//借助一个栈,模拟栈的后进先出(多考察性质)
bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
stack<int> st;
size_t pushi = 0, popi = 0;
while (pushi < pushV.size())
{
st.push(pushV[pushi++]); //先压入
while (!st.empty() && () == popV[popi])
{
st.pop();
popi++;
}
}
return st.empty();
}
};
while (!st.empty() && () == popV[popi])
{
st.pop();
popi++;
}
不能再判断语句出进行popi++
-
if (a == b++) {} 这个语句中,b++是一个后缀增量操作符。这意味着在比较a和b的值之前,b的原始值会被用来进行判断,但是不论判断的结果如何,b的值都会在判断之后自增1。
-
if (a == b) {b++;} 在这个语句中,首先进行a和b的比较,如果条件为真(即a等于b),那么花括号内的代码b++会被执行,b的值会增加1。如果条件为假,则不会执行花括号内的代码,b的值不会改变。
注意
栈,此题考查性质,栈最重要的就是后进先出。可以额外借助一个栈,去利用后进先出实现。
其次,前者到了数据的存储,要去想存储数据对应的数据结构,如何利用合适的数据结构完成数据合理利用。