java给定一个整数数组nums,有一个大小为k的滑动窗口从数组最左侧移动到数组的最右侧,每次只向右移动一位,求每次滑动窗口内的k个数字中的最大值组成的列表
时间: 2023-12-14 21:35:55 浏览: 76
滑动窗口的最大值.md
你好,这是一个典型的滑动窗口问题,可以使用双端队列来解决。
具体思路如下:
1. 初始化一个双端队列deque,用于存放数组索引
2. 遍历数组nums,对于每个元素nums[i],进行以下操作:
a. 判断队列头部的索引是否在滑动窗口内,如果不在则弹出队列头部
b. 判断队列尾部的索引对应的元素是否小于当前元素nums[i],如果是则弹出队列尾部
c. 将当前元素的索引加入队列尾部
d. 如果i>=k-1,则说明当前滑动窗口已经形成,将队列头部对应的元素加入结果列表
3. 返回结果列表
下面是Java代码实现:
```
public List<Integer> maxSlidingWindow(int[] nums, int k) {
List<Integer> result = new ArrayList<>();
Deque<Integer> deque = new LinkedList<>();
for (int i = 0; i < nums.length; i++) {
// 判断队列头部的索引是否在滑动窗口内,如果不在则弹出队列头部
if (!deque.isEmpty() && deque.peek() < i - k + 1) {
deque.poll();
}
// 判断队列尾部的索引对应的元素是否小于当前元素nums[i],如果是则弹出队列尾部
while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
deque.removeLast();
}
// 将当前元素的索引加入队列尾部
deque.offer(i);
// 如果i>=k-1,则说明当前滑动窗口已经形成,将队列头部对应的元素加入结果列表
if (i >= k - 1) {
result.add(nums[deque.peek()]);
}
}
return result;
}
```
阅读全文