检查数组是否可堆栈排序

Question

这里是问题：

我们想使用堆栈重新排列排序数组 [1, ..., N]。

例如：

 * push 1 then pop 1.
 * push 2 then push 3 then pop twice and get 3 then 2.

然后我们可以从[1,2,3]得到[1,3,2]

检查我们是否可以通过使用堆栈重新排列已排序的数组（升序）来获得给定的数组。

限制：

 * 0 < The size of the given array (N) <= 100,000
 * 1 <= The items of the given array <= N
 * No duplicates inside the given array

测试用例：

 * [1, 3, 2]: true
 * [3,1,2]: false

我想知道我从下面的代码中遗漏了什么。以下代码在某些测试用例上失败：

function solution(array) {
  const stack = [];
  let idx = 0;

  for (let i = 1; i <= array.length; i++) {
    if (i !== array[idx]) {
      stack.push(i);
    } else {
      idx++;
    }
  }

  for (idx; idx < array.length; idx++) {
    let item = stack.pop();
    if (item !== array[idx]) {
      return false;
    }
  }

  return true;
}

非常感谢！

Answer 1

逻辑不对，评论里已经说了，不能push然后pop。

最简单的方法是在数字不匹配时总是压入，如果匹配则弹出尽可能多的值：

function solution(array) {
    const stack = []
    let idx = 0
    for (let i = 1; i <= array.length; i++) {
        if (i != array[idx]) {
           stack.push(i)
        } else {
           idx++
           while (stack.length > 0 && stack[stack.length - 1] == array[idx]) {
               idx++
               stack.pop()
           }
        }
    }
    return idx == array.length
}

console.log(solution([1,3,2]))
console.log(solution([3,1,2]))

检查数组是否可堆栈排序

Check if an array is stack-sortable

javascript

arrays

sorting

algorithm

stack