思路都是一样的,y总视频里的思路,两个选择;
只不过我第一反应是用两个指针来做
class Solution {
public:
bool isPopOrder(vector<int> pushV,vector<int> popV) {
if(pushV.empty() && popV.empty()) return true;
if(pushV.size() != popV.size()) return false;
// 操作1: 当前栈顶元素与要出栈的元素相等,则pop
// 操作2: 当前栈顶元素与要出栈的元素不等,则push
// 最后若出栈序列仍然没有遍历至末尾,则false
int n = pushV.size();
unordered_map<int, bool> poped(n);
int i, j;
for( i = 0, j = 0; i < n && j < n; )
{
if(poped[pushV[i]])
{
i++;
continue;
}
if(pushV[i] == popV[j])
{
j++;
poped[pushV[i]] = true;
while(poped[pushV[i]]) i--;
}
else
{
i++;
}
}
if(j == n) return true;
return false;
}
};