// 声明一个长度为10的int数组var 
a [10]int
// 数组的长度是根据初始化值的个数来计算
b := [...]int{1, 2, 3}
// 定义了一个含有100个元素的数组r，最后一个元素被初始化为-1，其它元素都是用0初始化
c := [...]int{99: -1}

a := [2]int{1, 2}
b := [...]int{1, 2}
c := [2]int{1, 3}
fmt.Println(a == b, a == c, b == c) // "true false false"
d := [3]int{1, 2}
fmt.Println(a == d) // compile error: cannot compare [2]int == [3]int

var b bytes.Buffer // A Buffer needs no initialization.
b.Write([]byte("Hello "))
fmt.Fprintf(&b, "world!")
b.WriteTo(os.Stdout)

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isCompleteTree(root *TreeNode) bool {
    q := []*TreeNode{root}  // 队列
    var flag bool   // 标记是否已经碰到过左/右子树为空的节点

    // 开始层序遍历
    for i := 0; len(q) > 0; i++ {
        p := []*TreeNode{}  // p记录下一层节点
        for j := 0; j < len(q); j++ {
            cur := q[j] // 当前遍历节点

            if cur.Left != nil && !flag{
                // 左子树入队
                p = append(p, cur.Left)
            } else if cur.Left != nil && flag{
                // 已经遇到了左/右子树为空的节点，且当前节点的左子树非空，不是完全二叉树
                return false
            } else {
                flag = true
            }

            if cur.Right != nil && !flag{
                // 右子树入队
                p = append(p, cur.Right)
            } else if cur.Right != nil && flag{
                // 已经遇到了左/右子树为空的节点，且当前节点的右子树非空，不是完全二叉树
                return false
            } else {
                flag = true
            }
        }
        q = p   // 访问下一层节点
    }

    // 遍历完成，说明是完全二叉树
    return true
}

func longestConsecutive(nums []int) int {
    hashMap := map[int]bool{}  // 哈希表记录已有数字
    for _, v := range nums {    // 初始化哈希表
        hashMap[v] = true
    }
    var MaxLength int  // 数字连续的最长序列的长度

    for _, v := range nums {
        if !hashMap[v-1] {     // 没有等于v-1的元素，无需跳过
            curLength := 1  // 当前数字连续的序列长度
            i := 1
            for hashMap[v+i] {
                curLength++
                i++
            }
            if curLength > MaxLength {
                // 更新最大长度
                MaxLength = curLength
            }
        }
    }

    return MaxLength
}

func findMin(nums []int) int {
    low, high := 0, len(nums)-1
    var mid int

    for low < high {
        mid = (low+high)/2
        if nums[mid] > nums[high] {
            // 最小元素在mid左侧
            low = mid + 1
        } else {
            // 最小元素为mid或者在mid右侧
            high = mid
        }
    }

    return nums[low]
}

func findPeakElement(nums []int) int {
    max := nums[0]   // 最大值初始化为nums[0]
    maxIndex := 0   // 最大值元素的下标

    for i := 1; i < len(nums); i++ {    // 寻找最大值，最大值必为峰值
        if nums[i] > max {
            max = nums[i]
            maxIndex = i
        }
    }

    return maxIndex
}

func findPeakElement(nums []int) int {
    n := len(nums)  // 数组长度
    i := rand.Intn(n)   // 随机下标i
    right := (i+1 < n) && (nums[i+1] > nums[i])  // 向右走的标记，true为向右走，false为向左走

    for {
        if right {  // 向右走
            if i+1 < n && nums[i+1] > nums[i] {
                i++     // 继续向右
            } else {
                // 到达峰值
                break
            } 
        }

        if !right {    // 向左走
            if i-1 >= 0 && nums[i-1] >nums[i] {
                i--     // 继续向左
            } else {
                // 到达峰值
                break
            }   
        }
    }

    return i
}

func findPeakElement(nums []int) int {
    low, high := 0, len(nums)-1

    for low < high {
        mid := (low+high)/2
        
        if nums[mid] < nums[mid+1] {    // 右侧存在峰值
            low = mid + 1
        } else {    // 左侧存在峰值
            high = mid
        }
    }

    return low
}