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

[Mr.K 018]

原题：https://sstm.moe/topic/253265-每-日-算-法-挑-战-【第5期】/

已经到第二天了，还没看到第5期有任何正确答案。其实各位已经很接近正确答案了，但是都不约而同地忽略了这句话：

引用

需要说明的是，不同的输入序列需要用到的最小栈数可能是不同的，请对每个输入序列分别计算。

当然对任何输入序列都能用两个栈实现排序，相应算法楼里已经有人给出过了。实际上不考虑时间复杂度的话，可以构造出不止一个的用两个栈排序的算法，这里不再赘述。

但是，有没有只需1个栈呢？0个呢？这是本题的另一个考点。

对于0个栈的情况，很简单，当且仅当输入序列已经有序的时候，就不需要栈，输入一个输出一个就行。

对于1个栈的情况，这时需要模拟一下栈的操作了。目标很简单：第k次输出，要输出k。

假设我们刚刚输出完k-1，下一个轮到k了。由于我们不能访问栈中除栈顶元素以外的其他元素，所以k要么出现在以后的输入序列里。那么我们分下面几种情况讨论：

1）k在栈顶。直接弹出k输出即可，皆大欢喜；

2）k在输入序列的某处。我们可以把k之前的元素逐一压入栈中，然后输出这个k。

3）输入序列读完了，也没有发现k。这意味着k既不在栈顶，也不在输入序列里，只能在栈的内部。我们只有一个栈，实际上是访问不到k的。出现这种情况就意味着这个输入序列不能用一个栈排序。

不难发现，用一个栈排序出了上述方法外，别无他法。那么，我们可以在O(n)的时间内解决本题：

1. 遍历输入序列，若发现有序则输出0，结束；

2.进行上述模拟。若从1到n都成功“输出”，则输出1，结束；若出现情况3)，则输出2，结束。

------

所以说，这个题是不是比各位想象的简单呢？

[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

 

[Mr.K 018]

6 小时前, 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)

[Mr.K 018]

13 分钟前, yhz012 说道:

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

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

[yhz012]

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

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

现实来说倒是确实这样

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

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

[Mr.K 018]

2 分钟前, yhz012 说道:

现实来说倒是确实这样

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

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

有一些识别文法的工作时需要栈（下推有限自动机）的

现实中……比如说火车？只有一或两条轨道（这两条轨道相交，允许倒车），列车初始是无序的，现在想要有序地发车这样