剑指offer---64.滑动窗口的最大值

题目描述

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。

解法一：按题意

import java.util.*; public class Solution { public ArrayList<Integer> maxInWindows(int [] num, int size){ ArrayList<Integer> result = new ArrayList<>(); if(num==null||num.length==0||size==0||size>num.length) return result; int max = findMaxIndex(num,-1,0,size-1); result.add(num[max]); int index = size; while(index<num.length){ int tmpmax = findMaxIndex(num,max,index-size+1,index); result.add(num[tmpmax]); max = tmpmax; index++; } return result; } private int findMaxIndex(int[] num,int flag,int i,int j){ int max = -1; if(flag<i){ max = i; i++; while(i<=j){ if(num[max]<num[i]){ max = i; } i++; } }else{ max = num[j]>=num[flag]?j:flag; } return max; } }

解法二：利用堆

思路： 用lambda表达式会使时间复杂度太大

import java.util.*; public class Solution { public ArrayList<Integer> maxInWindows(int [] num, int size){ ArrayList<Integer> list = new ArrayList<>(); if(num==null||num.length==0||size==0||size>num.length) return list; PriorityQueue<Integer> pq = new PriorityQueue<>((o1,o2)->o2-o1); for(int i=0;i<size;i++){ pq.offer(num[i]); } list.add(pq.peek()); for(int i=1;i+size-1<num.length;i++){ pq.remove(num[i-1]); pq.offer(num[i+size-1]); list.add(pq.peek()); } return list; } }

解法三：利用队列保存

思路： 双端队列队头永远最大

import java.util.*; public class Solution { public ArrayList<Integer> maxInWindows(int [] num, int size){ ArrayList<Integer> list = new ArrayList<>(); if(num==null||num.length==0||size==0||size>num.length) return list; LinkedList<Integer> q = new LinkedList<>(); for(int i=0;i<num.length;i++){ if(!q.isEmpty()){ if(i>q.peek()+size-1){ q.poll(); } while(!q.isEmpty()&&num[i]>num[q.getLast()]){ q.removeLast(); } } q.offer(i); if(i+1>=size){ list.add(num[q.peek()]); } } return list; } }