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))

背景

推荐阅读

举例