This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

Given n integers, find a continuous subarray with the maximum mean and length K, and print the maximum mean.

Example: input: [1,12,-5,-6,50,3], k = 4 output: 12.75 explanation: maximum mean (12-5-6+50)/4 = 51/4 = 12.75 https://leetcode-cn.com/problems/maximum-average-subarray-i copyright belongs to The Collar network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.Copy the code

Thought analysis

  • The description of the topic is simple and easy to understand, and the solution is relatively easy. Sliding window can be used to solve the problem.
  • The average of sliding Windows is relatively simple, because only the number of numbers in the dynamic sum window can be calculated. Under the condition that the window size remains unchanged, the maximum sliding window sum can be calculated.

AC code

Public class DayCode {public static void main(String[] args) {int[] nums = new Int [] {1, 2, 12-5-6,50,3}; int k = 4; double ans = new DayCode().findMaxAverage(nums, k); System.out.println("ans is " + ans); } public double findMaxAverage(int[] nums, int k) { int tempSum = 0, maxSum = 0; for (int i = 0; i < k; i++) { tempSum += nums[i]; } maxSum = tempSum; for (int j = k; j < nums.length; j++) { tempSum -= nums[j-k]; tempSum += nums[j]; maxSum = Math.max(tempSum, maxSum); } return (double) maxSum / k; }}Copy the code

Submit tests:

AC smoothly!

conclusion

  • The time complexity of the above algorithm is O(n) and the space complexity is O(1).
  • The idea of sliding Windows is not complicated, but there are some boundaries and details to consider when implementing the code.
  • The idea of sliding Windows is also widely used in production, such as API interface flow limiting.
  • Stick to the daily question, come on!