package arrays;

import java.util.ArrayList;
import java.util.PriorityQueue;

/**题目:求滑动窗口的最大值个数
 * @Author Gavin
 * @date 2022年01月23日 16:27
 */
public class array_17 {
 /**
 *
 * 解题思路:
 * 暴力破解法
 */
 //Time:O(n*log(k)) Space:O(k)
 public static int[] solution(int[] nums,int k){
 if(nums==null || nums.length==0||k<=0)return nums;
 int n=nums.length;
 int[] result=new int[n-k+1];
 for (int left=0;left<=n-k;++left){
 int max=nums[left];
 for (int i = left; i < left + k; i++) {
 max=Math.max(max,nums[i]);
 }
 result[left]=max;
 }
 return result;
 }
 /**
 * 第二种方法,使用一个大顶堆
 */
 public ArrayList<Integer> solution_2(int[] num, int k) {
 ArrayList<Integer> result = new ArrayList<>();
 PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2 - o1);
 for (int i = 0; i < k; i++) {
 queue.add(num[i]);
 }
 result.add(queue.peek());
 for (int i = 0, j = k + i; j < num.length; i++, j++) {
 queue.remove(num[i]);//这里是remove,不是poll,移除指定元素
 queue.add(num[j]);
 result.add(queue.peek());
 }
 return result;
 }

}