手机应用内存使用分析与平稳性评估
手机应用内存使用分析与平稳性评估
https://www.nowcoder.com/practice/fca33811f9184ab48b1e9d2693cd6a0d
手机应用内存使用分析与平稳性评估
[题目链接](https://www.nowcoder.com/practice/fca33811f9184ab48b1e9d2693cd6a0d)
思路
给定数组 memoryUsage 和整数 k，要求计算每个长度为 k 的连续子数组中最大值与最小值的差值（波动范围）。
暴力做法
对于每个窗口，遍历窗口内所有元素求最大值和最小值。窗口个数为 ，每个窗口扫描
个元素，总时间复杂度
。当
和
都很大时会超时。
单调队列优化
经典的滑动窗口最值问题，可以用两个单调队列分别维护窗口内的最大值和最小值：
- 最大值队列（单调递减队列）：队头始终是当前窗口最大值。新元素入队时，从队尾弹出所有不大于它的元素。
- 最小值队列（单调递增队列）：队头始终是当前窗口最小值。新元素入队时，从队尾弹出所有不小于它的元素。
队列中存储的是下标，当队头下标超出窗口范围时将其弹出。当窗口形成（）后，波动范围 = 最大值队列队头对应的值 - 最小值队列队头对应的值。
每个元素最多入队一次、出队一次，因此总时间复杂度为 。
代码
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
};
复杂度分析
- 时间复杂度：
，其中
为数组长度。每个元素最多入队和出队各一次。
- 空间复杂度：
查看21道真题和解析