package question;


import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class Question239 {
 public static void main(String[] args) {
 //nums = [1,3,-1,-3,5,3,6,7], k = 3
 int[] nums = new int[]{1, 3, -1, -3, 5, 3, 6, 7};
 int k = 3;
 for (int i : new Question239().maxSlidingWindow(nums, k)) {
 System.out.println(i);
 }
 }

 //dp超时
 public int[] maxSlidingWindow2(int[] nums, int k) {
 int[] dp = Arrays.copyOf(nums, nums.length);
 for (int i = 2; i <= k; i++) {
 for (int j = 0; j + i - 1 < nums.length; j++) {
 dp[j] = Math.max(dp[j], nums[j + i - 1]);
 }
 }
 return Arrays.copyOf(dp, nums.length - k + 1);
 }

 public int[] maxSlidingWindow(int[] nums, int k) {
 Deque<Integer> deque = new LinkedList<>();
 int[] res = new int[nums.length - k + 1];
 for (int i = 0; i < k; i++) {
 while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
 deque.pollLast();
 }
 deque.offerLast(i);
 }
 res[0] = nums[deque.peekFirst()];
 for (int i = 1, j = k; j < nums.length; i++, j++) {
 if (!deque.isEmpty() && deque.peekFirst() < i) {
 deque.pollFirst();
 }
 while (!deque.isEmpty() && nums[j] >= nums[deque.peekLast()]) {
 deque.pollLast();
 }
 deque.offerLast(j);
 res[i] = nums[deque.peekFirst()];
 }
 return res;
 }
}