栈的压入弹出序列判断
栈的压入、弹出序列
https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&tqId=11174&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tPage=2
class Solution {
public:
bool IsPopOrder(vector<int> pushV,vector<int> popV) {
stack<int> sta;
if(pushV.empty()||popV.empty())
return false;
int popIndex=0;
for(int i=0;i<pushV.size();i++)
{
sta.push(pushV[i]);
while(!sta.empty()&&sta.top()==popV[popIndex])
{
sta.pop();
popIndex++;
}
}
return sta.empty();
}
};即模拟手动判断的过程
引入一个栈，当栈为空或者栈顶元素不等于此时出栈元素时，元素入栈
当栈顶元素等于出栈元素时，元素出栈，同时出栈序列index后移
最后如果辅助栈内还有元素，则出栈序列不是入栈序列
否则出栈序列是入栈序列
注意如果匹配的话，popIndex与弹出元素相同，所以不用拘泥于popIndex
比如：入栈：1，2，3，4，5 出栈：4,3,5,1,2
当入栈4四个元素1，2，3，4后，发现匹配到了第一个出栈序列4，则4出栈，popInex指向3，栈顶元素与3匹配，则3出栈，popIndex指向5，栈顶元素2与5不匹配，则最后一个元素5进栈，匹配到了出栈序列5，则5出栈，popIndex指向1，此时出栈元素只能是2与1不匹配
故辅助栈中还有1，2不为空，返回不匹配
