Sum of Maximum of Every Window
Given a list of integers nums and an integer k, find the maximum element in every contiguous window of size k. Return the sum of these maximum elements.
Method Signature
long sumOfWindowMaximums(List<Integer> nums, int k)
nums contains the integers.k is the size of each contiguous window.- Return the sum of the maximum elements of all windows.
Details
Process the contiguous windows from left to right. If nums contains n elements, there are exactly n - k + 1 windows of size k.
Constraints
1 ≤ nums.size() ≤ 100,000-1,000,000,000 ≤ nums[i] ≤ 1,000,000,0001 ≤ k ≤ nums.size()
Examples
Example 1
sumOfWindowMaximums(nums = [4, 2, 12, 3, 8, 7], k = 3)
Output: 44
The window maximums are 12, 12, 12, and 8. Their sum is 44.
Example 2
sumOfWindowMaximums(nums = [-5, -2, -8, -1], k = 2)
Output: -5
The window maximums are -2, -2, and -1. Their sum is -5.
Example 3
sumOfWindowMaximums(nums = [6, 1, 9], k = 3)
Output: 9
The entire list is the only window, and its maximum element is 9.