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

福大大架构师每日一题 · · 793 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

福大大答案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
    }
}

执行结果如下：