奉贤集团公司网站建设做团购网站

题目描述

有一套系统需升级，为减小系统升级期间的影响，需根据系统过去一段时间内的每小时平均访问数据，来预测

最佳升级时间窗。

现给长度为168（7*24）的整数数组，表示一个周期（假设从周一00:00到周日24:00）的每小时历史数据，最佳升级时间窗选择规则如下：

• 时间窗内累计用户访问量必须大于给定的容忍值。

• 时间窗必须是连续的x个小时，最大的x即为最佳升级时间窗，且不超过7*24.

• 时间窗允许跨周期，例如当前周期的第167小时到下一周期的第166axioms，是一个长度为168的时间窗。

请计算最佳升级时间窗，并返回其开始时间和结束时间的数组下标。如果存在多个最佳升级时间窗，返回开始时间下标最小的一个。

解答要求

时间限制：1000ms，内存限制：256MB

输入

第一行为整数n，表示给定的升级影响的容忍值，取值范围：[0, 2^31]。

第二行为7*24个整数，表示一个周期（7*24）的每个小时用户访问量，每个值的范围：[0, 2^31]。

输出

两个整数，分别表示所计算出的最佳升级时间窗的开始时间下标（包含）和结束时间下标（包含），不存在时返回 -1 -1 。

样例

输入样例

6
1 2 3 4 5 6 7 8 9 10 11 12 12 11 10 9 8 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 9 10 11 12 12 11 10 9 8 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 9 10 11 12 12 11 10 9 8 7 6 5 4 3 2 1

输出样例

22 25

编码实现（java）

    public static void main(String[] args) {int[] pvByHourWeekly = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1,1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1,1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};int[] result = getBestTimeWindow(pvByHourWeekly, 6);System.out.println(Arrays.stream(result).mapToObj(String::valueOf).collect(Collectors.joining(" ")));}public static int[] getBestTimeWindow(int[] pvByHourWeekly, int pvErrorTolerance) {int start = 0;int end = 0;int sum = 0;int maxWindow = 0;int maxStart = -1; // 初始值为-1，未找到最佳时间窗口for (int i = 0; i < pvByHourWeekly.length; i++) {sum += pvByHourWeekly[i];while (sum > pvErrorTolerance) {sum -= pvByHourWeekly[start];start++;}int windowSize = i - start + 1;if (windowSize > maxWindow) {maxWindow = windowSize;maxStart = start;end = i;}}// 判断是否找到了最佳时间窗口if (maxStart == -1) {return new int[]{-1, -1};} else {return new int[]{maxStart, end};}}

优化后代码

    public static void main(String[] args) {int[] pvByHourWeekly = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1,1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1,1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};int[] result = getBestTimeWindow(pvByHourWeekly, 6);System.out.println(Arrays.stream(result).mapToObj(String::valueOf).collect(Collectors.joining(" ")));}public static int[] getBestTimeWindow(int[] pvByHourWeekly, int pvErrorTolerance) {int start = 0;int end = 0;int sum = pvByHourWeekly[0];int maxWindow = 1;int maxStart = -1;for (int i = 1; i < pvByHourWeekly.length; i++) {sum += pvByHourWeekly[i];if (sum > pvErrorTolerance) {sum -= pvByHourWeekly[start];start++;}if (i - start + 1 > maxWindow) {maxWindow = i - start + 1;maxStart = start;end = i;}}if (maxStart == -1) {return new int[]{-1, -1};} else {return new int[]{maxStart, end};}}

输出结果

22 25Process finished with exit code 0