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

[题目链接](https://www.nowcoder.com/practice/fca33811f9184ab48b1e9d2693cd6a0d)

思路

给定数组 memoryUsage 和整数 k，要求计算每个长度为 k 的连续子数组中最大值与最小值的差值（波动范围）。

暴力做法

对于每个窗口，遍历窗口内所有元素求最大值和最小值。窗口个数为 $n - k + 1$ ，每个窗口扫描 $k$ 个元素，总时间复杂度 $O(nk)$ 。当 $n$ 和 $k$ 都很大时会超时。

单调队列优化

经典的滑动窗口最值问题，可以用两个单调队列分别维护窗口内的最大值和最小值：

最大值队列（单调递减队列）：队头始终是当前窗口最大值。新元素入队时，从队尾弹出所有不大于它的元素。
最小值队列（单调递增队列）：队头始终是当前窗口最小值。新元素入队时，从队尾弹出所有不小于它的元素。

队列中存储的是下标，当队头下标超出窗口范围时将其弹出。当窗口形成（ $i \geq k - 1$ ）后，波动范围 = 最大值队列队头对应的值 - 最小值队列队头对应的值。

每个元素最多入队一次、出队一次，因此总时间复杂度为 $O(n)$ 。

代码

C++
Java
Python3
JavaScript

class Solution {
public:
    vector<int> findFluctuations(vector<int>& memoryUsage, int k) {
        int n = memoryUsage.size();
        vector<int> res;
        deque<int> maxq, minq;
        for (int i = 0; i < n; i++) {
            while (!maxq.empty() && memoryUsage[maxq.back()] <= memoryUsage[i])
                maxq.pop_back();
            while (!minq.empty() && memoryUsage[minq.back()] >= memoryUsage[i])
                minq.pop_back();
            maxq.push_back(i);
            minq.push_back(i);
            if (maxq.front() <= i - k) maxq.pop_front();
            if (minq.front() <= i - k) minq.pop_front();
            if (i >= k - 1) {
                res.push_back(memoryUsage[maxq.front()] - memoryUsage[minq.front()]);
            }
        }
        return res;
    }
};

import java.util.*;

public class Solution {
    public int[] findFluctuations(int[] memoryUsage, int k) {
        int n = memoryUsage.length;
        int[] res = new int[n - k + 1];
        Deque<Integer> maxq = new ArrayDeque<>();
        Deque<Integer> minq = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!maxq.isEmpty() && memoryUsage[maxq.peekLast()] <= memoryUsage[i])
                maxq.pollLast();
            while (!minq.isEmpty() && memoryUsage[minq.peekLast()] >= memoryUsage[i])
                minq.pollLast();
            maxq.addLast(i);
            minq.addLast(i);
            if (maxq.peekFirst() <= i - k) maxq.pollFirst();
            if (minq.peekFirst() <= i - k) minq.pollFirst();
            if (i >= k - 1) {
                res[i - k + 1] = memoryUsage[maxq.peekFirst()] - memoryUsage[minq.peekFirst()];
            }
        }
        return res;
    }
}

from collections import deque
from typing import List

class Solution:
    def findFluctuations(self, memoryUsage: List[int], k: int) -> List[int]:
        n = len(memoryUsage)
        res = []
        maxq = deque()
        minq = deque()
        for i in range(n):
            while maxq and memoryUsage[maxq[-1]] <= memoryUsage[i]:
                maxq.pop()
            while minq and memoryUsage[minq[-1]] >= memoryUsage[i]:
                minq.pop()
            maxq.append(i)
            minq.append(i)
            if maxq[0] <= i - k:
                maxq.popleft()
            if minq[0] <= i - k:
                minq.popleft()
            if i >= k - 1:
                res.append(memoryUsage[maxq[0]] - memoryUsage[minq[0]])
        return res

function findFluctuations(memoryUsage, k) {
    const n = memoryUsage.length;
    const res = [];
    const maxq = [];
    const minq = [];
    let maxHead = 0, minHead = 0;
    for (let i = 0; i < n; i++) {
        while (maxq.length > maxHead && memoryUsage[maxq[maxq.length - 1]] <= memoryUsage[i])
            maxq.pop();
        while (minq.length > minHead && memoryUsage[minq[minq.length - 1]] >= memoryUsage[i])
            minq.pop();
        maxq.push(i);
        minq.push(i);
        if (maxq[maxHead] <= i - k) maxHead++;
        if (minq[minHead] <= i - k) minHead++;
        if (i >= k - 1) {
            res.push(memoryUsage[maxq[maxHead]] - memoryUsage[minq[minHead]]);
        }
    }
    return res;
}
module.exports = {
    findFluctuations: findFluctuations
};

复杂度分析

时间复杂度： $O(n)$ ，其中 $n$ 为数组长度。每个元素最多入队和出队各一次。
空间复杂度： $O(n)$ ，两个单调队列和结果数组各占 $O(n)$ 空间。