Scala实现双栈队列在HackerRank超时问题排查

超时核心原因 #

1. 倒栈逻辑不合理
   最常见的错误是每次执行出队（操作2）或查看队首（操作3）时，不管输出栈是否为空，都重复将输入栈的元素倒入输出栈。这种做法会让每次操作的时间复杂度变成O(n)，大数据量下必然超时。
   正确逻辑：仅当输出栈为空时，才将输入栈的所有元素一次性倒入输出栈（此时输出栈的顶部就是队列的队首）；若输出栈非空，直接操作输出栈即可。每个元素最多被倒两次，均摊时间复杂度为O(1)。

2. 低效的栈实现
   如果用Scala不可变List模拟栈（用::添加、head/tail获取/删除顶部元素），每次操作都会创建新的链表节点，频繁操作会产生大量临时对象，GC开销极大，拖慢性能。

3. 频繁IO操作
   若每次循环都调用StdIn.readLine()读取输入，多次IO调用的开销在大数据量测试用例中会累积成超时。

Scala高效栈/容器选择 #

• 优先使用scala.collection.mutable.ArrayDeque：它是基于数组的双端队列，栈操作（addOne入栈、removeLast出栈、last取栈顶）均为O(1)时间，数组结构的缓存友好性远优于链表实现的mutable.Stack，性能更高。
• 避免使用不可变List作为栈：除非是极小数据量场景，否则不可变集合的对象创建开销会成为性能瓶颈。

优化后的示例代码 #

import scala.collection.mutable.ArrayDeque

object Main {
  def main(args: Array[String]): Unit = {
    // 一次性读取所有输入，减少IO开销
    val lines = scala.io.Source.stdin.getLines().toArray
    val inStack = ArrayDeque[Int]()  // 存放入队元素的栈
    val outStack = ArrayDeque[Int]() // 存放待出队元素的栈（栈顶为队首）
    
    val n = lines(0).toInt
    for (i <- 1 to n) {
      val parts = lines(i).split(" ")
      parts(0) match {
        case "1" =>
          // 入队：直接压入输入栈
          inStack.addOne(parts(1).toInt)
        case "2" =>
          // 出队：输出栈空时先倒栈，再弹出栈顶
          if (outStack.isEmpty) {
            while (inStack.nonEmpty) {
              outStack.addOne(inStack.removeLast())
            }
          }
          outStack.removeLast()
        case "3" =>
          // 查队首：输出栈空时先倒栈，再取栈顶
          if (outStack.isEmpty) {
            while (inStack.nonEmpty) {
              outStack.addOne(inStack.removeLast())
            }
          }
          println(outStack.last)
      }
    }
  }
}

关键优化点 #

• 倒栈逻辑仅在输出栈为空时触发，避免重复操作
• 用ArrayDeque替代低效的栈实现，提升操作效率
• 一次性读取所有输入，消除多次IO调用的开销

内容的提问来源于stack exchange，提问作者Simple Fellow