友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
239. Sliding Window Maximum
Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.
Example:
Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7]
Explanation:
Window position Max
--------------- -----
[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] 7Note:
You may assume k is always valid, 1 ≤ k ≤ input array’s size for non-empty array.
Follow up:
Could you solve it in linear time?
思路分析
最佳解决方案是单调栈：下面最大，单调递增。
使用单调栈，即使数组最大元素在最前面也没事，可以通过判断栈的长度，超过指定长度则将第一个元素删除，那么第一个元素就是当前窗口的最大值。
-
一刷
-
二刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/**
* Runtime: 9 ms, faster than 85.37% of Java online submissions for Sliding Window Maximum.
* Memory Usage: 56.6 MB, less than 6.25% of Java online submissions for Sliding Window Maximum.
*
* Copy from: https://leetcode-cn.com/problems/sliding-window-maximum/solution/hua-dong-chuang-kou-zui-da-zhi-by-leetcode-3/[滑动窗口最大值 - 滑动窗口最大值 - 力扣（LeetCode）]
*/
public int[] maxSlidingWindow(int[] nums, int k) {
if (Objects.isNull(nums) || nums.length == 0 || k == 0) {
return new int[0];
}
if (k == 1) {
return nums;
}
int n = nums.length;
int[] left = new int[n];
left[0] = nums[0];
int[] right = new int[n];
right[n - 1] = nums[n - 1];
for (int i = 1; i < n; i++) {
if (i % k == 0) {
left[i] = nums[i];
} else {
left[i] = Math.max(left[i - 1], nums[i]);
}
int j = n - i - 1;
if ((j + 1) % k == 0) {
right[j] = nums[j];
} else {
right[j] = Math.max(nums[j], right[j + 1]);
}
}
int[] result = new int[n - k + 1];
for (int i = 0; i < n - k + 1; i++) {
result[i] = Math.max(left[i + k - 1], right[i]);
}
return result;
}
/**
* Runtime: 25 ms, faster than 30.23% of Java online submissions for Sliding Window Maximum.
* Memory Usage: 48.5 MB, less than 6.25% of Java online submissions for Sliding Window Maximum.
*/
public int[] maxSlidingWindowMax(int[] nums, int k) {
if (Objects.isNull(nums) || nums.length == 0 || k == 0) {
return new int[0];
}
List<Integer> integers = new ArrayList<>();
for (int i = 0; i < nums.length - k + 1; i++) {
int max = Integer.MIN_VALUE;
for (int j = i; j < i + k; j++) {
max = Math.max(max, nums[j]);
}
integers.add(max);
}
int[] result = new int[integers.size()];
for (int i = 0; i < integers.size(); i++) {
result[i] = integers.get(i);
}
return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
* 参考 https://leetcode.cn/problems/sliding-window-maximum/solutions/543426/hua-dong-chuang-kou-zui-da-zhi-by-leetco-ki6m/[239. 滑动窗口最大值 - 官方题解^]
*
* @author D瓜哥 · https://www.diguage.com
* @since 2024-07-06 16:20:24
*/
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || nums.length == 0) {
return new int[0];
}
int len = nums.length;
Deque<Integer> deque = new LinkedList<>();
for (int i = 0; i < k; i++) {
while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
deque.pollLast();
}
deque.offerLast(i);
}
int[] result = new int[len - k + 1];
result[0] = nums[deque.peekFirst()];
for (int i = k; i < len; i++) {
while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
deque.pollLast();
}
deque.offerLast(i);
while (deque.peekFirst() <= i - k) {
deque.pollFirst();
}
result[i - k + 1] = nums[deque.peekFirst()];
}
return result;
}