|
概念
一种具有单调性的队列，分为单调递增队列和单调递减队列。
适合场景
维护区间最值，即，适合解决RMQ（rang maximum/minimum query）问题，也称之为滑动窗口区间最值问题。
若维护区间最小值，则需要维护一个单调递增的序列；若维护区间最大值，则需要维护一个单调递减的序列。
维护单调队列性值的操作
入队操作：队尾入队，会把之前破坏单调性的元素都从队尾移出（维护单调性）。
出队操作：如果队首元素超出区间范围，就将元素从队首出队。
1.1 习题
一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
public int[] maxSlidingWindow(int[] nums, int k) {
Deque<Integer> deque = new LinkedList<>();
int[] result = new int[nums.length - k + 1];
int idx = 0;
for (int i = 0; i < nums.length; i++) {
while (!dequeue.isEmpty() && nums[i] > nums[deque.peekLast()]) {
deque.pollLast();
}
deque.offerLast(i);
if (i - deque.getFirst() == k) {
deque.pollFirst();
}
if (i + 1 < k) {
continue;
}
result[idx++] = nums[deque.peekFirst()];
}
return result;
}
请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
若队列为空，pop_front 和 max_value 需要返回 -1
示例 1：
输入:
[“MaxQueue”,“push_back”,“push_back”,“max_value”,“pop_front”,“max_value”]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]
class MaxQueue {
Queue<Integer> queue;
Deque<Integer> deque;
public MaxQueue() {
queue = new LinkedList<>();
deque = new LinkedList<>();
}
public int max_value() {
return deque.isEmpty() ? -1 : deque.peekFirst();
}
public void push_back(int value) {
queue.offer(value);
while (!deque.isEmpty() && deque.peekLast() < value) {
deque.pollLast();
}
deque.offerLast(value);
}
public int pop_front() {
if (queue.isEmpty()) {
return -1;
}
if (!deque.isEmpty() && queue.peek().equals(deque.peekFirst())) {
deque.pollFirst();
}
return queue.poll();
}
}
返回 A 的最短的非空连续子数组的长度，该子数组的和至少为 K 。
如果没有和至少为 K 的非空子数组，返回 -1
示例 ：
输入：A = [2,-1,2], K = 3
输出：3
分析：前缀和数组 + 单调递增队列
子数组和 => 前缀和数组，
前缀和数组两元素差值的最小值为k，即，若固定前缀和数组末尾后，该固定末尾的子数组两元素差值需要尽可能大，即直接用当前前缀和数组固定末尾元素减去前缀和数组的最小值，得到的就是那个最大的差值，若这个差值>=k，则，为了找到长度更短的子数组，可以继续向后找到前缀和数组的次小值，看是否满足差值>=k；直到差值不满足>=k。最后一个满足条件的就是固定末尾的最短子数组。==》 由此分析，可得，除了需要一个前缀和数组外，还需要维护这个前缀和数组的最小值的单调递增队列；
对该前缀和数组从前后扫描，以前缀和数组的下一个元素为固定末尾，寻找满足题意的子数组，因为需要找比之前的子数组还短的数组，所以之前从单调队列队首弹出的元素都不满足条件，可以基于此单调队列从前至后继续寻找。
public int shortestSubarray(int[] nums, int k) {
Deque<Integer> deque = new LinkedList<>();
int[] sum = new int[nums.length + 1];
for (int i = 0; i < nums.length; i++) {
sum[i + 1] = sum[i] + nums[i];
}
int pos = -1;
int ans = -1;
for (int i = 0; i < sum.length; i++) {
while (!deque.isEmpty() && sum[i] < sum[deque.peekLast()]) {
deque.pollLast();
}
deque.offerLast(i);
while (!deque.isEmpty() && sum[i] - sum[deque.peekFirst()] >= k) {
pos = deque.pollFirst();
}
if (pos != -1 && (i - pos < ans || ans == -1)) {
ans = i - pos;
}
}
return ans;
}
给你一个整数数组 nums ，和一个表示限制的整数 limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。
如果不存在满足条件的子数组，则返回 0 。
示例 1：
输入：nums = [8,2,4,7], limit = 4
输出：2
解释：所有子数组如下：
[8] 最大绝对差 |8-8| = 0 <= 4.
[8,2] 最大绝对差 |8-2| = 6 > 4.
[8,2,4] 最大绝对差 |8-2| = 6 > 4.
[8,2,4,7] 最大绝对差 |8-2| = 6 > 4.
[2] 最大绝对差 |2-2| = 0 <= 4.
[2,4] 最大绝对差 |2-4| = 2 <= 4.
[2,4,7] 最大绝对差 |2-7| = 5 > 4.
[4] 最大绝对差 |4-4| = 0 <= 4.
[4,7] 最大绝对差 |4-7| = 3 <= 4.
[7] 最大绝对差 |7-7| = 0 <= 4.
因此，满足题意的最长子数组的长度为 2 。
L为最长的子数组，若最大值 - 最小值 <= limit，则该子数组内任意两个元素之间的绝对值差一定<=limit；故，一定存在满足条件的小于L的子数组；一定不存在满足条件的大于L的子数组；
由此，此求最长子数组长度可转化为二分查找的01模型中的找最后一个0的问题。
class Solution {
public int longestSubarray(int[] nums, int limit) {
return binarySearch(nums, 1, nums.length, limit);
}
private int binarySearch(int[] nums, int l, int r, int limit) {
int mid = 0;
while (l < r) {
mid = (l + r + 1) >> 1;
if (check(nums, mid, limit)) {
l = mid;
} else {
r = mid - 1;
}
}
return l;
}
private boolean check(int[] nums, int length, int limit) {
Deque<Integer> deque_min = new LinkedList<>();
Deque<Integer> deque_max = new LinkedList<>();
for (int i = 0; i < nums.length; i++) {
while (!deque_max.isEmpty() && nums[i] > nums[deque_max.peekLast()]) {
deque_max.pollLast();
}
while (!deque_min.isEmpty() && nums[i] < nums[deque_min.peekLast()]) {
deque_min.pollLast();
}
deque_max.offerLast(i);
deque_min.offerLast(i);
if (i + 1 < length) continue;
if (i - deque_max.peekFirst() == length) {
deque_max.pollFirst();
}
if (i - deque_min.peekFirst() == length) {
deque_min.pollFirst();
}
if (nums[deque_max.peekFirst()] - nums[deque_min.peekFirst()] <= limit) {
return true;
}
}
return false;
}
}
|