题解 | 最小活动范围
最小活动范围
https://www.nowcoder.com/practice/f5e7c034bb5046089ce774e37e5342d9
- 单调栈。找到窗口最小的，且窗口缩小后，下一个最小的。符合单调栈的应用场景
- 窗口化在 L18
import java.util.*;
public class Solution {
public int[] minSlidingWindow (int[] nums, int k) {
final int n = nums.length;
int[] ans = new int[n - k + 1];
Deque<Integer> q = new ArrayDeque<>();
for (int i = 0; i < k; ++i) {
while (!q.isEmpty() && nums[q.getLast()] >= nums[i]) {
q.removeLast();
}
q.addLast(i);
}
ans[0] = nums[q.getFirst()];
for (int i = k; i < n; ++i) {
final int l = i - k + 1;
if (q.getFirst() < l) {
q.removeFirst();
}
while (!q.isEmpty() && nums[q.getLast()] >= nums[i]) {
q.removeLast();
}
q.addLast(i);
ans[i - k + 1] = nums[q.getFirst()];
}
return ans;
}
}
哔哩哔哩公司福利 596人发布