2021-03-31：给定一个数组arr，给定一个值v。求子数组平均值小于等于v的最长子数组长度。

2021-03-31：给定一个数组arr，给定一个值v。求子数组平均值小于等于v的最长子数组长度。

福大大 答案2021-03-31：

这道题是昨天每日一题的变种。数组每个元素减v，然后求<=0的最长子数组长度。

1.前缀和+有序表。时间复杂度O(N*lgN)。无代码。

2.滑动窗口。时间复杂度O(N)。这道题用自然智慧想不到，需要练敏感度。有代码。

数组每个元素减v。

minSum数组，最小累加和，以i开头最小值。

minSumEnd数组，以i开头最小值，右边界在哪里。

采用滑动窗口，右指针每次移动多位，左指针每次移动一位。

虽然用到了两个for循环，但是右指针不回退，所以复杂度是O(N)。

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

package main

import "fmt"

//https://github.com/algorithmzuo/algorithmbasic2020/blob/master/src/class40/Code04_AvgLessEqualValueLongestSubarray.java

func main() {

    arr := []int{1000, -10, 60, -60, 3, 1, -2, 1, 10}

    v := 5

    ret := ways1(arr, v)

    fmt.Println(ret)

}

func ways1(arr []int, v int) int {

    arrLen := len(arr)

    if arrLen == 0 {

        return 0

    }

    //数组的所有值都减掉平均值

    for i := 0; i < arrLen; i++ {

        arr[i] -= v

    }

    //最小累加和数组

    //最小累加和数组的右边界

    minSums := make([]int, arrLen)

    minSumEnds := make([]int, arrLen)

    minSums[arrLen-1] = arr[arrLen-1]

    minSumEnds[arrLen-1] = arrLen - 1

    for i := arrLen - 2; i >= 0; i-- {

        if minSums[i+1] < 0 {

            minSums[i] = arr[i] + minSums[i+1]

            minSumEnds[i] = minSumEnds[i+1]

        } else {

            minSums[i] = arr[i]

            minSumEnds[i] = i

        }

    }

    R := 0

    sum := 0

    ans := 0

    for L := 0; L < arrLen; L++ {

        //R循环右扩

        for R < arrLen && sum+minSums[R] <= 0 {

            sum += minSums[R]

            R = minSumEnds[R] + 1

        }

        //统计答案

        ans = getMax(ans, R-L)

        //L右扩前，需要处理

        if R > L {

            sum -= arr[L]

        } else {

            R = L + 1

        }

    }

    //数组修改了，需要还原

    for i := 0; i < arrLen; i++ {

        arr[i] += v

    }

    return ans

}

func getMax(a int, b int) int {

    if a > b {

        return a

    } else {

        return b

    }

}

执行结果如下：

---

左神java代码

评论

2021-03-31：给定一个数组arr，给定一个值v。求子数组平均值小于等于v的最长子数组长度。的相关教程结束。