最后,检查辅助栈和弹出队列是否均为空。
时间复杂度是 O(N^2),空间复杂度是 O(N)。代码实现如下:
// ac地址:https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106
// 原文地址:https://xxoo521.com/2020-01-31-stack-pop-push/
/**
*
- @param {string[]} pushV
@param {string[]} popV
*/
function IsPopOrder(pushV, popV) {
const stack = []; // 辅助栈 pushV.forEach(v => {
if (v === popV[0]) {
popV.shift();
let i = 0;
const popVLength = popV.length;
for (; i < popVLength; ++i) {
if (stack[stack.length - 1] === popV[i]) {
stack.pop();
} else {
break;
}
}
popV.splice(0, i);
} else {
stack.push(v);
}
}); return !stack.length && !popV.length;
}