1. 题目描述

输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。

例如序列 1、2、3、4、5 是某栈的压栈序列,序列 4、5、3、2、1 是该压栈序列对应的一个弹出序列,但 4、3、5、1、2 就不可能是该压栈序列的弹出序列。

2. 思路分析

栈的题目还是借助“辅助栈”。大体思路如下:

  1. 将入栈序列的元素依次入辅助栈
  2. 检查辅助栈顶元素和弹栈序列栈顶元素是否一致:
  • 元素一致,弹出辅助栈元素,弹栈序列指针后移
  • 不一致,回到第一步

需要注意的是,过程中的边界条件检查(多试试几种情况)。除此之外,由于 js 不提供指针运算,所以用标记下标的方法代替指针。

3. 代码实现

/**
 * 获得栈顶元素
 * @param {Array} stack
 */
function getStackTop(stack) {
  if (!Array.isArray(stack)) {
    return null;
  }

  if (!stack.length) {
    return null;
  }

  return stack[stack.length - 1];
}

/**
 * 第二个参数是否是该栈的弹出顺序
 * @param {Array} pushOrder
 * @param {Array} popOrder
 * @return {Boolean}
 */
function check(pushOrder, popOrder) {
  if (
    !pushOrder.length ||
    !popOrder.length ||
    pushOrder.length !== popOrder.length
  ) {
    return false;
  }

  const stack = []; // 辅助栈
  let i = 0,
    j = 0; // i: 压入序列指针; j: 弹出序列指针

  while (j < popOrder.length) {
    for (; i < pushOrder.length && popOrder[j] !== getStackTop(stack); ++i) {
      stack.push(pushOrder[i]);
    }

    if (popOrder[j] !== getStackTop(stack)) {
      return false;
    }

    stack.pop();
    ++j;
  }

  return true;
}

/**
 * 以下是测试代码
 */

console.log(check([1, 2, 3, 4], [4, 3, 2, 1]));

console.log(check([1, 2, 3, 4, 5], [4, 5, 3, 2, 1]));

console.log(check([1, 2, 3, 4, 5], [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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60