难度: Hard
Submission
运行时间: 127 ms
内存: 17.1 MB
from collections import deque
class Solution:
def findMaxAverage(self, nums: List[int], k: int) -> float:
# (count, sum)
stack = deque()
st = 0
N = len(nums)
for i in range(0, k):
st += nums[i]
ans = st / k
ct = k
for i in range(1, N - k + 1):
st += nums[i + k - 1]
ct += 1
s1 = nums[i - 1]
c1 = 1
# S0 / C0 >= S1 / C1
while stack and stack[-1][1] * c1 >= s1 * stack[-1][0]:
c0, s0 = stack.pop()
c1 += c0
s1 += s0
stack.append((c1, s1))
# S0 / C0 <= st / ct
while stack and stack[0][1] * ct <= st * stack[0][0]:
c0, s0 = stack.popleft()
ct -= c0
st -= s0
ans = max(ans, st / ct)
return ans
Explain
此题解采用滑动窗口加上双端队列（deque）的方式来求解问题。首先，通过滑动窗口计算初始大小为k的子数组的平均值。随后，继续滑动窗口并在每一步尝试调整子数组的开始和结束位置，以便找到可能的最大平均值。这一过程中使用了双端队列来维护当前窗口的子数组信息。每次移动时，从前面移除元素并可能从队尾合并较小的平均值子数组，从而不断更新当前的最大平均值。通过队列操作，我们能够有效地计算每一个新窗口的平均值，并比较它与已知的最大平均值。
时间复杂度: O(N)
空间复杂度: O(N)
from collections import deque
class Solution:
def findMaxAverage(self, nums: List[int], k: int) -> float:
# 初始化双端队列，用于存储子数组的大小和总和
stack = deque()
# 初始子数组的总和
st = 0
# 数组的长度
N = len(nums)
# 计算第一个窗口的总和
for i in range(0, k):
st += nums[i]
# 初始的最大平均值
ans = st / k
# 窗口的初始大小
ct = k
# 从第二个元素开始滑动窗口
for i in range(1, N - k + 1):
# 向窗口添加新元素，窗口扩展
st += nums[i + k - 1]
ct += 1
s1 = nums[i - 1]
c1 = 1
# 合并小的子数组，保证队尾的平均值最大
while stack and stack[-1][1] * c1 >= s1 * stack[-1][0]:
c0, s0 = stack.pop()
c1 += c0
s1 += s0
stack.append((c1, s1))
# 调整窗口大小，尝试找到更大的平均值
while stack and stack[0][1] * ct <= st * stack[0][0]:
c0, s0 = stack.popleft()
ct -= c0
st -= s0
ans = max(ans, st / ct)
return ans
Explore
滑动窗口的起始大小k通常是根据题目要求或数据特性确定的。在本题中，k可能是一个给定的初始值，表示要求计算的最小子数组的长度。选择合适的k对算法的效果有显著影响：较小的k可能让算法更频繁地更新最大平均值，而较大的k则可能减少更新次数但增大了每次计算的数据量。初始窗口大小k是平衡算法效率和精度的一个关键因素。
此条件确保在队列中，较新添加的子数组（平均值较小）与前一个子数组合并时，不会导致平均值下降。具体例子：假设队列末尾有一个子数组平均值为3（总和为6，元素个数为2），即`(2, 6)`。现在新加入的元素为1，形成新子数组`(1, 1)`。按照合并条件`6 * 1 >= 1 * 2`，即`6 >= 2`，条件满足，所以这两个子数组应合并为`(3, 7)`，新的平均值为`7 / 3`，仍然保持了队列中平均值不减的原则。
这个条件检查当前窗口的总平均值是否大于队列首部的子数组平均值。如果是，移除队首的子数组能提高整体窗口的平均值。例如，如果整体窗口平均值（`st / ct`）高于队首子数组的平均值，通过移除这部分较低平均的子数组，剩余部分的平均值可能增加，从而尝试找到一个更大的平均值。这是通过不断调整窗口大小来优化当前窗口的平均值。
是的，元素的操作次数可能少于两次。这通常发生在元素在被加入到窗口后很快就被移除，而没有经过队列中的合并过程。例如，如果一个元素被添加到窗口后，随即因为不满足窗口的平均值提高条件而被移除，那么该元素只被操作了一次。这种情况较少见，通常发生在窗口平均值与新加入元素差异较大时。