今天在做题的时候遇到了个有趣的问题，先上代码：

单队列的实现

type pos struct{
    x int
    y int
}

func numEnclaves(grid [][]int) int {
    enclave_num := 0

    queue := make([]pos, 0, 0)

    is_land := false
    for i:=0;i<len(grid);i++{
        for j:=0;j<len(grid[0]);j++{
            if grid[i][j] == 0{
                continue
            }

            queue = append(queue, pos{i, j})

            block_num := 0
            is_land = false
            for ;len(queue)>0;{
                pos_ := queue[0]
                x, y := pos_.x, pos_.y

                if grid[x][y] == 0{
                    queue = queue[1:]
                    continue
                }
                grid[x][y] = 0
                block_num++
                if x == 0 || x == len(grid)-1 || y == 0 || y == len(grid[0])-1{
                    is_land = true
                }
                if x+1<len(grid) && grid[x+1][y] == 1{
                    queue = append(queue, pos{x+1, y})
                }
                if x-1>=0 && grid[x-1][y] == 1{
                    queue = append(queue, pos{x-1, y})
                }
                if y+1<len(grid[0]) && grid[x][y+1] == 1{
                    queue = append(queue, pos{x, y+1})
                }
                if y-1>=0 && grid[x][y-1] == 1{
                    queue = append(queue, pos{x, y-1})
                }
                queue = queue[1:]
            }
            if is_land == false{
                enclave_num += block_num
            }
        }
    }
    return enclave_num
}

双队列的实现

type pos struct{
    x int
    y int
}

func numEnclaves(grid [][]int) int {
    enclave_num := 0

    queue := make([]pos, 0, 0)
    new_queue := make([]pos, 0, 0)

    is_land := false
    for i:=0;i<len(grid);i++{
        for j:=0;j<len(grid[0]);j++{
            if grid[i][j] == 0{
                continue
            }

            queue = append(queue, pos{i, j})

            block_num := 0
            is_land = false
            for ;len(queue)>0;{
                new_queue = new_queue[:0]
                for _, pos_ := range queue{
                    x, y := pos_.x, pos_.y
                    if grid[x][y] == 0{
                        continue
                    }
                    block_num++
                    if x == 0 || x == len(grid)-1 || y == 0 || y == len(grid[0])-1{
                        is_land = true
                    }
                    if x+1<len(grid) && grid[x+1][y] == 1{
                        new_queue = append(new_queue, pos{x+1, y})
                    }
                    if x-1>=0 && grid[x-1][y] == 1{
                        new_queue = append(new_queue, pos{x-1, y})
                    }
                    if y+1<len(grid[0]) && grid[x][y+1] == 1{
                        new_queue = append(new_queue, pos{x, y+1})
                    }
                    if y-1>=0 && grid[x][y-1] == 1{
                        new_queue = append(new_queue, pos{x, y-1})
                    }
                    grid[x][y] = 0
                }
                queue = queue[:0]
                queue, new_queue = new_queue, queue
            }
            if is_land == false{
                enclave_num += block_num
            }
        }
    }
    return enclave_num
}

性能对比

单队列

双队列

单队列的代码更简洁，且只定义了一个slice，直觉上似乎应该时空效率更高，但实际上单队列的实现方式会消耗更多的内存，而且会频繁申请新空间。双队列会复用之前的底层结构，所以申请新空间的概率大大降低。