励志：🔔半身浸江，全身如林，所谓万丈深渊，下去也是前程万里。我启程了，你呢?
FIFO队列
滑动窗口
题：933. 最近的请求次数
写一个 RecentCounter 类来计算特定时间范围内最近的请求。
请你实现 RecentCounter 类：
- RecentCounter() 初始化计数器，请求数为 0 。
- int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去 3000 毫秒内发生的所有请求数（包括新请求）。确切地说，返回在 [t-3000, t] 内发生的请求数。
保证 每次对 ping 的调用都使用比之前更大的 t 值。
示例：
输入：
["RecentCounter", "ping", "ping", "ping", "ping"]
[[], [1], [100], [3001], [3002]]
输出：
[null, 1, 2, 3, 3]
解释：
RecentCounter recentCounter = new RecentCounter();
recentCounter.ping(1); // requests = [1]，范围是 [-2999,1]，返回 1
recentCounter.ping(100); // requests = [1, 100]，范围是 [-2900,100]，返回 2
recentCounter.ping(3001); // requests = [1, 100, 3001]，范围是 [1,3001]，返回 3
recentCounter.ping(3002); // requests = [1, 100, 3001, 3002]，范围是 [2,3002]，返回 3
提示：
1 <= t <= 109
保证每次对 ping 调用所使用的 t 值都 严格递增
至多调用 ping 方法 104 次
解：
解题思路：队列的应用
AC代码：
class RecentCounter {
Queue<Integer> queue;
public RecentCounter() {
queue = new LinkedList<>();
}
public int ping(int t) {
queue.offer(t);
while(queue.peek() < t - 3000) {
queue.poll();
}
return queue.size();
}
}
/**
* Your RecentCounter object will be instantiated and called as such:
* RecentCounter obj = new RecentCounter();
* int param_1 = obj.ping(t);
*/- 时间复杂度：O（Q），Q为ping的次数
- 空间复杂度：O（W），W为存储ping的数目，最大为3000
剑指 Offer II 042. 最近请求次数
题：剑指 Offer II 041. 滑动窗口的平均值
给定一个整数数据流和一个窗口大小，根据该滑动窗口的大小，计算滑动窗口里所有数字的平均值。
实现 MovingAverage 类：
- MovingAverage(int size) 用窗口大小 size 初始化对象。
- double next(int val) 成员函数 next 每次调用的时候都会往滑动窗口增加一个整数，请计算并返回数据流中最后 size 个值的移动平均值，即滑动窗口里所有数字的平均值。
示例：
输入：
inputs = ["MovingAverage", "next", "next", "next", "next"]
inputs = [[3], [1], [10], [3], [5]]
输出：
[null, 1.0, 5.5, 4.66667, 6.0]
解释：
MovingAverage movingAverage = new MovingAverage(3);
movingAverage.next(1); // 返回 1.0 = 1 / 1
movingAverage.next(10); // 返回 5.5 = (1 + 10) / 2
movingAverage.next(3); // 返回 4.66667 = (1 + 10 + 3) / 3
movingAverage.next(5); // 返回 6.0 = (10 + 3 + 5) / 3
提示：
1 <= size <= 1000
-105 <= val <= 105
最多调用 next 方法 104 次解：
解题思路：队列的简单应用
AC代码：
class MovingAverage {
Queue<Integer> queue;
int maxSize;
double res = 0;
/** Initialize your data structure here. */
public MovingAverage(int size) {
queue = new LinkedList<>();
maxSize = size;
}
public double next(int val) {
while(queue.size() >= maxSize) {
res -= queue.poll();
}
queue.offer(val);
res += val;
return res / queue.size();
}
}
/**
* Your MovingAverage object will be instantiated and called as such:
* MovingAverage obj = new MovingAverage(size);
* double param_1 = obj.next(val);
*/- 时间复杂度：O（1）
- 空间复杂度：O（1）
BFS
单源BFS
多源BFS
题：542. 01 矩阵
给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。
示例 1：
输入：mat = [[0,0,0],[0,1,0],[0,0,0]]
输出：[[0,0,0],[0,1,0],[0,0,0]]示例 2：
输入：mat = [[0,0,0],[0,1,0],[1,1,1]]
输出：[[0,0,0],[0,1,0],[1,2,1]]
提示：
m == mat.length
n == mat[i].length
1 <= m, n <= 104
1 <= m * n <= 104
mat[i][j] is either 0 or 1.
mat 中至少有一个 0
解：
解题思路：多源BFS
AC代码：
class Solution {
// 遍历方向
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public int[][] updateMatrix(int[][] mat) {
int m = mat.length;
int n = mat[0].length;
int[][] res = new int[m][n];
boolean[][] visited = new boolean[m][n];
Queue<int[]> queue = new LinkedList<>();
// 多源, i为纵轴, j为横轴
for(int i = 0; i < m; i ++) {
for(int j = 0; j < n; j ++) {
if(mat[i][j] == 0) {
queue.offer(new int[]{i, j});
visited[i][j] = true;
}
}
}
// BFS
while(!queue.isEmpty()) {
int[] dist = queue.poll();
int i = dist[0];
int j = dist[1];
// 四个方向遍历
for(int d = 0; d < 4; d ++) {
int ni = i + dirs[d][0];
int nj = j + dirs[d][1];
if(ni >= 0 && ni < m && nj >= 0 && nj < n && !visited[ni][nj]) {
res[ni][nj] = res[i][j] + 1;
queue.offer(new int[]{ni, nj});
visited[ni][nj] = true;
}
}
}
return res;
}
}- 时间复杂度：O（mn），mn为矩阵元素个数
- 空间复杂度：O（mn），mn为矩阵元素个数
