1 条题解
-
0
需要注意这道题中的窗口长度不是固定的，而是由窗口内最大值和最小值之差决定，这个差值需要小于等于k。
思路
因为要计算最大值和最小值之差，所以需要维护两个单调队列，记录序号和最大最小值
过程中使用双指针L和R模拟滑动窗口, 设置L=1，然后枚举右端点R，计算当前窗口的最大值与最小值之差是否满足≤k，若满足更新窗口最大长度ans，若不满足，则不断移动左指针L直到当前窗口内最大值与最小值之差≤k。
单调队列的实现： 求最大值： 当队列非空且队尾的数≤a[r]，就让队尾的数出队。 求最小值：当队列非空且队尾的数≥a[r]，就让队尾的数出队。
注意：在移动左指针 L 时，需要把两个队列中序号小于L的元素从队首出队，因为这些元素已经不在滑动窗口范围内了。
维护单调队列
while (h1 <= t1 && a[q1[t1]] <= a[r]) t1--; q1[++t1] = r; while (h2 <= t2 && a[q2[t2]] >= a[r]) t2--; q2[++t2] = r;更新滑动窗口
while (a[q1[h1]] - a[q2[h2]] > k && l < r) { l++; while (h1 <= t1 && q1[h1] < l) h1++; while (h1 <= t2 && q2[h2] < l) h2++; } ans = max(ans, r - l + 1);
董一骏
MOD
@ 2024-3-29 16:09:13
- 1