leetcode 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 = , and k = 3
Output:
Explanation:
Window position Max
--------------- -----
-35367 3
1 5367 3
13 [-1-35] 367 5
13-1 [-353] 67 5
13-1-3 7 6
13-1-35 7
Note:
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?
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int i = 0, j;
int n = nums.length;
List <Integer> list = new ArrayList<>();
List <Integer> max = new ArrayList<>();
for(j = 0; j < n ; j++){
max.add(nums);
if(j - i + 1>= k){
list.add(Collections.max(max));
max.remove(i);
}
}
int[] ret = list.stream().mapToInt(x ->x).toArray();
return ret;
}
}
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums.length == 0 || k == 0) return nums;
int j = 0, n = nums.length;
int[] arr = new int;
for(int i = 0; i< n ; i++){
int max = Integer.MIN_VALUE;
if(i - j +1 >= k){
for(int m = j; m <= i; m++){
max = Math.max(max, nums);
}
arr = max;
j++;
}
}
return arr;
}
}
monotonic queue!
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums.length == 0) return nums;
int n = nums.length;
int[] res = new int;
ArrayDeque<Integer> index = new ArrayDeque<>();
for(int i =0; i< n; i++){
while(!index.isEmpty() && nums > nums){
index.pollLast();
}
index.offerLast(i);
if(i - k + 1 >= 0){
res = nums;
}
if(i - k + 1>= index.peekFirst()) index.pop();
}
return res;
}
}
页:
[1]