给定一个数组arr,给定一个值v。求子数组平均值小于等于v的最长子数组长度。
  KRe60ogUm4le 18天前 74 0

给定一个数组arr,给定一个值v。求子数组平均值小于等于v的最长子数组长度。

这道题是昨天每日一题的变种。数组每个元素减v,然后求<=0的最长子数组长度。
1.前缀和+有序表。时间复杂度O(N*lgN)。无代码。
2.滑动窗口。时间复杂度O(N)。这道题用自然智慧想不到,需要练敏感度。有代码。
数组每个元素减v。
minSum数组,最小累加和,以i开头最小值。
minSumEnd数组,以i开头最小值,右边界在哪里。
采用滑动窗口,右指针每次移动多位,左指针每次移动一位。
虽然用到了两个for循环,但是右指针不回退,所以复杂度是O(N)。

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

package main

import "fmt"

//https:///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
    }
}

执行结果如下:

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

【版权声明】本文内容来自摩杜云社区用户原创、第三方投稿、转载,内容版权归原作者所有。本网站的目的在于传递更多信息,不拥有版权,亦不承担相应法律责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@moduyun.com

  1. 分享:
最后一次编辑于 18天前 0

暂无评论

推荐阅读
KRe60ogUm4le
最新推荐 更多

2024-05-31