小编Mik*_*ike的帖子

最近我陷入了困境.算法部分需要计算长度为K的滑动窗口的最大元素之和.其中K的范围是1 <= K <= N(阵列的N长度).

示例如果我有一个数组A作为5,3,12,4
长度为1的5 + 3 + 12 + 4 = 24
滑动窗口:长度为2的5 + 12 + 12 = 29
滑动窗口:长度为3的12 + 12 = 24
滑动窗口:长度为4的滑动窗口:12

Final answer is 24,29,24,12.

我试过这个O(N ^ 2).对于长度为K的每个滑动窗口,我可以用O(N)计算最大值.由于K高达N.因此,总体复杂度变为O(N ^ 2).
我正在寻找O(N)或O(NlogN)或与此算法类似的东西,因为N可能高达10 ^ 5.
注意:数组中的元素可以大到10 ^ 9,因此输出最终答案为模10 ^ 9 + 7

编辑:我实际上想要找到K的每个值(即从0到N)的答案线性时间或O(NlogN)不在O(KN)或O(KNlogN)中,其中K = {1,2,3,...... N}

我有这样的课

class Calculate {
    int operation(int a, int b){
         return Math.max(a,b);
    }
    int calc(int a, int b){
        int x=100+a*b;
        int y=a+a*b;
        retun operation(x,y);
    }
    int calc1(int a, int b){
        int x=100+a*b;
        int y=b+a*b;
        return operation(x,y);
    }
}

现在我创建这个类的两个对象,因为
Calculate obj1=new Calculate();
Calculate obj2=new Calculate();
我想要类的函数操作计算为obj1返回两个值的最大值,并返回obj2的两个值的最小值.可以这样做吗？
我只能想到创建两个不同的类Calculate1和Calculate2,并在Calculate1中将操作定义为最大值,在Calculate2中定义最小值,并将其定义为与其相同.我希望在不定义两个类的情况下也可以使用一些更简单