优化

830.单调栈

原题链接

给定一个长度为N的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出-1。

输入格式

第一行包含整数N，表示数列长度。

第二行包含N个整数，表示整数数列。

输出格式

共一行，包含N个整数，其中第i个数表示第i个数的左边第一个比它小的数，如果不存在则输出-1。

数据范围

1≤N≤105
1≤数列中元素≤109

输入样例：

5
3 4 2 7 5

输出样例：

-1 3 -1 2 2

Go 代码 使用 scanf

package main

import (
    "fmt"
)


func main() {
    const N = 100010
    stack := make([]int, N) // 单调栈
    var tt int              // 栈顶指针

    var n int
    fmt.Scan(&n) // 读取第一行操作次数
    for i := 0; i < n; i++ {
        var x int
        fmt.Scan(&x)
        for tt > 0 && stack[tt] >= x {
            tt--
        }
        if tt != 0 {
            fmt.Print(stack[tt], " ")
        } else {
            fmt.Print(-1, " ")
        }

        tt++
        stack[tt] = x
    }

}

Go 代码 使用 scanf 优化输出

package main

import (
    "fmt"
    "strings"
    "strconv"
)


func main() {
    const N = 100010
    stack := make([]int, N) // 单调栈
    var tt int              // 栈顶指针

    var n int
    fmt.Scan(&n) // 读取第一行操作次数
    var res []string
    for i := 0; i < n; i++ {
        var x int
        fmt.Scan(&x)
        for tt > 0 && stack[tt] >= x {
            tt--
        }
        if tt != 0 {
            res = append(res, strconv.Itoa(stack[tt]))
        } else {
            res = append(res, "-1")
        }

        tt++
        stack[tt] = x
    }
    fmt.Println(strings.Join(res, " "))
}

Go 代码 使用 bufio.Scanner

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var scanner *bufio.Scanner

func main() {
    scanner = bufio.NewScanner(os.Stdin)
    bs := make([]byte, 20000*1024)
    scanner.Buffer(bs, len(bs))
    scanner.Split(bufio.ScanWords)

    const N = 100010
    stack := make([]int, N) // 单调栈
    var tt int              // 栈顶指针

    var n = readWord() // 读取第一行操作次数
    for i := 0; i < n; i++ {
        var x = readWord()
        for tt > 0 && stack[tt] >= x {
            tt--
        }
        if tt != 0 {
            fmt.Print(stack[tt], " ")
        } else {
            fmt.Print(-1, " ")
        }

        tt++
        stack[tt] = x
    }

}

func readWord() int {
    scanner.Scan()
    var res int
    res, _ = strconv.Atoi(scanner.Text())
    return res
}

Go 代码 使用 bufio.Scanner 优化输出

package main

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

var scanner *bufio.Scanner

func main() {
    scanner = bufio.NewScanner(os.Stdin)
    bs := make([]byte, 20000*1024)
    scanner.Buffer(bs, len(bs))
    scanner.Split(bufio.ScanWords)

    const N = 100010
    stack := make([]int, N) // 单调栈
    var tt int              // 栈顶指针
    var res []string // 定义结果数组

    var n = readWord() // 读取第一行操作次数
    for i := 0; i < n; i++ {
        var x = readWord()
        for tt > 0 && stack[tt] >= x {
            tt--
        }
        if tt != 0 {
            res = append(res, strconv.Itoa(stack[tt]))
        } else {
            res = append(res, "-1")
        }

        tt++
        stack[tt] = x
    }
    fmt.Println(strings.Join(res, " "))
}

func readWord() int {
    scanner.Scan()
    var res int
    res, _ = strconv.Atoi(scanner.Text())
    return res
}

总结 优化结果

因为优化了输入和输出，从 4162 ms 到 158 ms。