Go ACM模式处理输入输出

背景

面试时ACM模式较多，力扣以核心代码模式为主，特地训练下ACM模式处理输入输出

举例

使用常规输入输出：

package main

import (
    "fmt"
    "strings"
)

func main() {
    var n, k int
    fmt.Scanln(&n, &k)
    list := make([]int, n)
    for i := 0; i < n; i++ {
        fmt.Scan(&list[i])
    }
    max, min := slidingWindow(list, k)
    // 直接for循环输出也可
    fmt.Println(strings.Trim(fmt.Sprint(min), "[]"))
    fmt.Println(strings.Trim(fmt.Sprint(max), "[]"))
}

func slidingWindow(list []int, k int) (max, min []int) {
    var maxWindow, minWindow []int
    // 单调递减队列
    maxPush := func(i int) {
        for len(maxWindow) > 0 && list[maxWindow[len(maxWindow)-1]] < list[i] {
            maxWindow = maxWindow[:len(maxWindow)-1]
        }
        maxWindow = append(maxWindow, i)
    }
    // 单调递增队列
    minPush := func(i int) {
        for len(minWindow) > 0 && list[minWindow[len(minWindow)-1]] > list[i] {
            minWindow = minWindow[:len(minWindow)-1]
        }
        minWindow = append(minWindow, i)
    }
    for i := 0; i < k; i++ {
        maxPush(i)
        minPush(i)
    }
    max = append(max, list[maxWindow[0]])
    min = append(min, list[minWindow[0]])
    for i := k; i < len(list); i++ {
        maxPush(i)
        minPush(i)
        // 删除超出窗口的部分
        for maxWindow[0] < i-k+1 {
            maxWindow = maxWindow[1:]
        }
        for minWindow[0] < i-k+1 {
            minWindow = minWindow[1:]
        }
        max = append(max, list[maxWindow[0]])
        min = append(min, list[minWindow[0]])
    }
    return
}

结果就是有三个超时，其他通过，可自行尝试

分析下原因，每次fmt.Scan时都会进行一次系统调用，如果N较大，那时间开销相对就比较大，我们可以使用bufio库将数据直接读取到缓存中，整体只需要一次系统调用，时间开销要小很多

相应的，输出时如果我们选择for循环每次print一个数据，那时间开销也会很长，但将数据通过strings.Trim(fmt.Sprint(min), "[]")处理好之后再输出，总共两次fmt.Println系统开销要小很多。同时我们也可以把结果放到缓冲区中，再通过Flush将数据写出

我们先来看处理输入：

import (
    "bufio"
    "fmt"
    "os"
    "strings"
)

func main() {
    var n, k int
    fmt.Scanln(&n, &k)
    list := make([]int, n)

    //fmt.Scanf("%d %d/n", &n, &k)
    // os.Stdin标准输入，写入到缓存中
    in := bufio.NewReader(os.Stdin)
    // os.Stdout标准输出
    // out := bufio.NewWriter(os.Stdout)
    // 从缓存中读取数据
    for i := 0; i < n; i++ {
        fmt.Fscan(in, &list[i])
    }

    max, min := slidingWindow(list, k)
    fmt.Println(strings.Trim(fmt.Sprint(min), "[]"))
    fmt.Println(strings.Trim(fmt.Sprint(max), "[]"))
  return
}

修改后，所有数据点可通过

我们再来看下输出，这时我们用了两次fmt.Println，也就是会进行两次系统调用，那我们如果将结果写入输出的缓存中，最后os.Flush是不是可以对时间进一步优化呢，原则上是这样的：

func main() {
    var n, k int
    fmt.Scanln(&n, &k)
    list := make([]int, n)

    //fmt.Scanf("%d %d/n", &n, &k)
    in := bufio.NewReader(os.Stdin)
    out := bufio.NewWriter(os.Stdout)

    for i := 0; i < n; i++ {
        fmt.Fscan(in, &list[i])
    }

    max, min := slidingWindow(list, k)
    //fmt.Println(strings.Trim(fmt.Sprint(min), "[]"))
    //fmt.Println(strings.Trim(fmt.Sprint(max), "[]"))
    // 将数据处理好后，写入out缓存中
    fmt.Fprint(out, fmt.Sprint(strings.Trim(fmt.Sprint(min), "[]")+"\n"+strings.Trim(fmt.Sprint(max), "[]")))
    // 将缓存中的数据刷新到io.Writer
    out.Flush()
  return
}

最后的运行结果是有一个点报MLE了（按照第二种写法，那个点是100.16MB）

这个也比较好理解，对于数据量比较变态的情况，及时将数据输出，可以预防MLE，所有结果合起来再输出，就有可能会超出规定内存

当然，输入也有可能会超出默认缓存大小，这个时候需要根据实际情况进行调整，例如 https://www.acwing.com/blog/content/28740/ 中提到的：

特殊场合当一次输入超大时：3302. 表达式求值

将输入缓存设置为20000 * 1024

in = bufio.NewScanner(os.Stdin)
bs = make([]byte, 20000 * 1024)

in.Buffer(bs, len(bs))

背景

推荐阅读

举例