很多人都说是求最大值，想了想确实是这样。我来说一下我的思路。
首先计算出所有值的和及平均值，然后设置两个指针分别在第一个元素和最后一个元素的位置。
接下来考虑移动指针的规则，因为是向中心移动，由于区间长度减小所以平均值有可能会增大也可能会减小，但是可以确定的是移动较小值的指针总会比移动较大值的指针之后的平均值大。【数据量相同，总和相同，移出去一个肯定时移除较小值平均值较大】将移动之后的平均值和现在平均值进行比较，思路有点类似于lc的盛水问题。
因此，代码复杂度必须要降到O(n)，我估计题的限制应该也是O(n)才能AC，不知道各位用快排的能A不？
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int [] a = new int [n];
int sum = 0;
for(int i = 0; i < n; i++){
int x = sc.nextInt();
a[i] = x;
sum += x;
}
int x=0, y = n -1;
int avg = sum/n;
while(x < y)
{
if(a[x] < a[y])
{
sum-=a[x];
x++;
avg = Math.max(avg,sum/(y - x + 1));
}
else
{
sum-=a[y];
y--;
avg = Math.max(avg,sum/(y - x + 1));
}
}
System.out.println(avg);
全部评论
(0) 回帖