题目内容

小塔是一名手机应用开发工程师，需要分析应用在手机上的内存使用情况。他有一个数组$memoryUsage$，其中$memoryUsage$[$i$]表示应用在第$i$秒的内存使用量(以$MB$为单位)。为了评估应用的稳定性，你需要找出每个连续$k$秒内的内存使用量的波动范围(即最大值与最小值的差值)，并返回这些波动范围。

思路

为了求解区间的最大值和最小值之间的差值，可以分别找到区间内的最大值和最小值。虽然暴力求解的方法时间复杂度为 (O(n^3))，显然不够高效，但我们可以使用更优化的算法：单调队列。

以求解区间最大值为例，我们可以利用双端队列（deque）来高效地解决这个问题。具体方法是：

1. 双端队列的维护： 维护一个单调递减的队列。队列中的元素按从大到小的顺序排列，且队列的相对顺序与原数组中的元素顺序一致。因此，队首元素即为当前区间的最大值。

2. 队列操作规则：

   • 元素入队： 在队列中，新元素入队时，需要将所有小于新元素的元素从队尾弹出，以保持队列的单调递减性质。