题目链接

手机应用内存使用分析与平稳性评估

题目描述

给定一个表示内存使用量的数组 memoryUsage 和一个整数 k。需要找出所有长度为 k 的连续子数组（滑动窗口）中的内存使用量波动范围，即每个窗口内最大值与最小值的差。返回一个包含所有波动范围的数组。

思路分析

这是一个经典的滑动窗口最值问题。

暴力解法

最直观的方法是遍历所有可能的窗口。总共有 个窗口，对于每个窗口，我们再花费 的时间来查找其中的最大值和最小值。总时间复杂度为 ，在 和 较大时会超时。

优化：单调队列

为了优化性能，我们可以使用单调队列（通常由双端队列 Deque 实现）来高效地维护滑动窗口内的最大值和最小值。这种数据结构可以确保我们在 的时间内获取当前窗口的最值。

我们需要两个单调队列：

  1. 一个递减队列 max_deque，用于寻找窗口最大值。
  2. 一个递增队列 min_deque，用于寻找窗口最小值。

下面以递减队列 max_deque 的工作原理为例：

  • 队列性质：队列中存储元素的下标，并且这些下标在原数组中对应的值是严格单调递减的。因此，队首的下标始终指向当前窗口的最大值。
  • 窗口滑动过程：
    1. 添加新元素：当新元素 memoryUsage[i] 进入窗口时，我们从 max_deque 的队尾开始，移除所有比 memoryUsage[i] 小的元素的下标。这保证了队列的单调性。然后，将新元素的下标 i 加入队尾。
    2. 移除旧元素：在添加新元素之前，检查队首的下标是否已经滑出窗口（即下标小于 i - k + 1）。如果是，则从队首移除该下标。
  • 获取最大值：完成上述操作后，max_deque 的队首元素就是当前窗口最大值的下标。

递增队列 min_deque 的工作原理与此类似，只是维护的值是单调递增的。

通过在一次遍历中同时维护这两个单调队列，我们可以在遍历到每个窗口的末尾时，立即获得该窗口的最大值和最小值，从而计算出波动范围。由于每个元素的下标最多只入队和出队一次，整个算法的时间复杂度为 。

代码

#include <vector>
#include <deque>

using namespace std;

// 核心逻辑封装在 Solution 类中，以匹配牛客网的判题模板
class Solution {
public:
    vector<int> findFluctuations(vector<int>& memoryUsage, int k) {
        if (memoryUsage.empty() || k <= 0 || k > memoryUsage.size()) {
            return {};
        }

        vector<int> result;
        deque<int> max_deque, min_deque;
        
        for (int i = 0; i < memoryUsage.size(); ++i) {
            // 维护最大值队列（单调递减）
            while (!max_deque.empty() && memoryUsage[max_deque.back()] <= memoryUsage[i]) {
                max_deque.pop_back();
            }
            max_deque.push_back(i);

            // 维护最小值队列（单调递增）
            while (!min_deque.empty() && memoryUsage[min_deque.back()] >= memoryUsage[i]) {
                min_deque.pop_back();
            }
            min_deque.push_back(i);

            // 移除滑出窗口的旧下标
            if (max_deque.front() <= i - k) {
                max_deque.pop_front();
            }
            if (min_deque.front() <= i - k) {
                min_deque.pop_front();
            }
            
            // 当窗口形成后，计算波动范围
            if (i >= k - 1) {
                result.push_back(memoryUsage[max_deque.front()] - memoryUsage[min_deque.front()]);
            }
        }
        
        return result;
    }
};


import java.util.LinkedList;
import java.util.Deque;

// 实际提交时，只需提交 Solution 类的部分
class Solution {
    public int[] findFluctuations(int[] memoryUsage, int k) {
        if (memoryUsage == null || memoryUsage.length == 0 || k <= 0 || k > memoryUsage.length) {
            return new int[0];
        }

        int[] result = new int[memoryUsage.length - k + 1];
        Deque<Integer> maxDeque = new LinkedList<>();
        Deque<Integer> minDeque = new LinkedList<>();

        for (int i = 0; i < memoryUsage.length; i++) {
            // 维护最大值队列
            while (!maxDeque.isEmpty() && memoryUsage[maxDeque.peekLast()] <= memoryUsage[i]) {
                maxDeque.pollLast();
            }
            maxDeque.offerLast(i);

            // 维护最小值队列
            while (!minDeque.isEmpty() && memoryUsage[minDeque.peekLast()] >= memoryUsage[i]) {
                minDeque.pollLast();
            }
            minDeque.offerLast(i);

            // 移除滑出窗口的旧下标
            if (maxDeque.peekFirst() <= i - k) {
                maxDeque.pollFirst();
            }
            if (minDeque.peekFirst() <= i - k) {
                minDeque.pollFirst();
            }
            
            // 当窗口形成后，计算波动范围
            if (i >= k - 1) {
                result[i - k + 1] = memoryUsage[maxDeque.peekFirst()] - memoryUsage[minDeque.peekFirst()];
            }
        }
        return result;
    }
}


from collections import deque

# 核心逻辑封装在 Solution 类中，以匹配牛客网的判题模板
class Solution:
    def findFluctuations(self, memoryUsage, k):
        if not memoryUsage or k <= 0 or k > len(memoryUsage):
            return []

        result = []
        max_deque = deque()
        min_deque = deque()

        for i, val in enumerate(memoryUsage):
            # 维护最大值队列
            while max_deque and memoryUsage[max_deque[-1]] <= val:
                max_deque.pop()
            max_deque.append(i)

            # 维护最小值队列
            while min_deque and memoryUsage[min_deque[-1]] >= val:
                min_deque.pop()
            min_deque.append(i)
            
            # 移除滑出窗口的旧下标
            if max_deque[0] <= i - k:
                max_deque.popleft()
            if min_deque[0] <= i - k:
                min_deque.popleft()
                
            # 当窗口形成后，计算波动范围
            if i >= k - 1:
                result.append(memoryUsage[max_deque[0]] - memoryUsage[min_deque[0]])
                
        return result

算法及复杂度

  • 算法：滑动窗口 + 单调队列
  • 时间复杂度：，其中 是数组 memoryUsage 的长度。每个元素的下标最多被压入和弹出队列一次。
  • 空间复杂度：，双端队列中最多存储 个元素的下标。