golang solution


  • 0
    C
    import "math"
    
    func findMaxAverage(nums []int, k int) float64 {
        sum := make([]float64, len(nums))
        sum[0] = float64(nums[0])
        for i := 1; i < len(nums); i++ {
            sum[i] = sum[i-1] + float64(nums[i])
        }
            
        var q []int
        max := sum[len(nums)-1] / float64(len(nums))
        for i := k-1; i < len(nums); i++ {
            for len(q) >= 2 && density(sum, q[len(q)-2], i-k) >= density(sum, q[len(q)-1], i-k) {
                q = q[0 : len(q)-1]
            }
            q = append(q, i-k+1)
            for len(q) >= 2 && density(sum, q[0], i) <= density(sum, q[1], i) {
                q = q[1:len(q)]
            }
            max = math.Max(density(sum, q[0], i), max)
        }
        
        return max
    }
    
    func density(sum []float64, left, right int) float64 {
        if left == 0 {
            return sum[right] / float64(right + 1)
        }
        return (sum[right] - sum[left-1]) / float64(right - left + 1)
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.