输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
对顺序压入、弹出后序列，其入栈前、出栈后的序列刚好相反，故反向遍历两序列，并引入临时栈以处理不连续压入、弹出时栈中遗留的元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| class Solution {
public:
bool IsPopOrder(vector<int> pushV,vector<int> popV) {
stack<int> temp;
auto push_i = pushV.rbegin();
auto pop_i = popV.begin();
while (pop_i != popV.end())
{
if (temp.size() != 0 && temp.top() == *push_i)
{
temp.pop();
push_i++;
}
else if (*push_i == *pop_i)
{
push_i++;
pop_i++;
}
else
{
temp.push(*pop_i);
pop_i++;
}
}
if (temp.size() == 0)
{
return true;
}
else
{
return false;
}
}
};
|