娱乐 每日算法挑战·第5期题解

[yhz012]

居然直接写栈么

实际上不用实际的空间来开栈也可以做吧

stackFlag = False
next = 0
prev = 0
temp = 0

usedFlag = False

for x in A:
  if stackFlag:
    if x != temp:
      return 2
    else:
      temp = temp - 1
      if temp == next:
        stackFlag = False
        next = prev + 1
  else:
    if x != next:
      usedFlag = True
      prev = x
      stackFlag = True
      temp = prev - 1
    else:
      next = next + 1
return 1 if usedFlag else 0

 

[yhz012]

9 分钟前, Mr.K 018 说道:

可以啊，模拟了栈的算法直观一点，好想。

而且时空复杂度都是一样的

时间复杂度倒是没问题，空间复杂度直接开栈最坏可以是O(n)的吧，逻辑算的话只需要O(1)

[yhz012]

3 分钟前, Mr.K 018 说道:

主要是这个题数据没那么大，O(n)也够用的

现实来说倒是确实这样

当然真要现实考虑的话真的会有不得不用这种方法做排序的情况么？

我记得好像有哪个模型是单带图灵机+栈来着？