2021-尊龙凯时网址

2021-07-17：一个不含有的数组可以代表一圈，每个位置的值代表山的高度。比如， {3,1,2,4,5}、{4,5,3,1,2}或{1,2,4,5,3}都代表同样结构的环形山。山峰a和山峰b能够相互看见的条件为: 1.如果a和b是同一座山，认为不能相互看见，2.如果a和b是不同的山，并且在环中相邻，认为可以相互看见，3.如果a和b是不同的山，并且在环中不相邻，假设两座山高度的最小值为min，1)如果a通过顺时针方向到b的途中没有高度比min大的山峰，认为a和b可以相互看见，2)如果a通过逆时针方向到b的途中没有高度比min大的山峰，认为a和b可以相互看见。两个方向只要有一个能看见，就算a和b可以相互看见。给定一个不含有负数且没有重复值的数组 arr，请返回有多少对山峰能够相互看见。进阶问题：给定一个不含有负数但可能含有重复值的数组arr，返回有多少对山峰能够相互看见。

福大大答案2021-07-17：

时间紧，见代码。

代码用golang编写。代码如下：

package main
import (

    "container/list"

    "fmt"

)
func main() {

    arr := []int{3, 1, 2, 4, 5, 3, 1, 2, 4, 5}

    ret := getvisiblenum(arr)

    fmt.println(ret)

}
// 栈中放的记录，

// value就是指，times是收集的个数

type record struct {

    value int

    times int

}
func newrecord(value int) *record {

    ret := &record{}

    ret.value = value

    ret.times = 1

    return ret

}
func twoselectone(c bool, a int, b int) int {

    if c {

        return a

    } else {

        return b

    }

}
func getvisiblenum(arr []int) int {

    if len(arr) < 2 {

        return 0

    }

    n := len(arr)

    maxindex := 0

    // 先在环中找到其中一个最大值的位置，哪一个都行

    for i := 0; i < n; i   {

        maxindex = twoselectone(arr[maxindex] < arr[i], i, maxindex)

    }

    stack := list.new().init()

    // 先把(最大值,1)这个记录放入stack中

    stack.pushback(newrecord(arr[maxindex]))

    // 从最大值位置的下一个位置开始沿next方向遍历

    index := nextindex(maxindex, n)

    // 用“小找大”的方式统计所有可见山峰对

    res := 0

    // 遍历阶段开始，当index再次回到maxindex的时候，说明转了一圈，遍历阶段就结束

    for index != maxindex {

        // 当前数要进入栈，判断会不会破坏第一维的数字从顶到底依次变大

        // 如果破坏了，就依次弹出栈顶记录，并计算山峰对数量

        for stack.back().value.(*record).value < arr[index] {

            k := stack.back().value.(*record).times

            stack.remove(stack.back())

            // 弹出记录为(x,k)，如果k==1，产生2对; 如果k>1，产生2*k   c(2,k)对。

            res  = getinternalsum(k)   2*k

        }

        // 当前数字arr[index]要进入栈了，如果和当前栈顶数字一样就合并

        // 不一样就把记录(arr[index],1)放入栈中

        if stack.back().value.(*record).value == arr[index] {

            stack.back().value.(*record).times  

        } else { // >

            stack.pushback(newrecord(arr[index]))

        }

        index = nextindex(index, n)

    }

    // 清算阶段开始了

    // 清算阶段的第1小阶段

    for stack.len() > 2 {

        times := stack.back().value.(*record).times

        stack.remove(stack.back())

        res  = getinternalsum(times)   2*times

    }

    // 清算阶段的第2小阶段

    if stack.len() == 2 {

        times := stack.back().value.(*record).times

        stack.remove(stack.back())

        res  = getinternalsum(times)   twoselectone(stack.back().value.(*record).times == 1, times, 2*times)

    }

    // 清算阶段的第3小阶段

    res  = getinternalsum(stack.back().value.(*record).times)

    stack.remove(stack.back())

    return res

}
// 如果k==1返回0，如果k>1返回c(2,k)

func getinternalsum(k int) int {

    return twoselectone(k == 1, 0, k*(k-1)/2)

}
// 环形数组中当前位置为i，数组长度为size，返回i的下一个位置

func nextindex(i int, size int) int {

    return twoselectone(i < (size-1), i 1, 0)

}