美文网首页
滑动窗口问题

滑动窗口问题

作者: 培根好吃 | 来源:发表于2018-08-27 19:19 被阅读0次

用到了一个双端队列 LinkedList

package com.ryan.offer;

import java.util.ArrayList;
import java.util.LinkedList;


public class SlideWindow {

    public static void main(String[] args) {
        
      int[] arr= {1,3,5,7,9,11,13,15};
      getCurrentWindowMaxValue(arr, 4);
      System.out.println(getCurrentWindowMaxValue(arr, 3));
    }
    public static ArrayList<Integer> getCurrentWindowMaxValue(int[] arr, int size) {
        if (arr == null || size < 1 || arr.length < size) {
            return null;
        }
        ArrayList<Integer> list=new ArrayList<>();
        LinkedList<Integer> qmax = new LinkedList<Integer>();
        for(int i=0;i<arr.length;i++) {
                if(qmax.isEmpty()) {
                qmax.add(i);
            }else {
                while((!qmax.isEmpty()&&(arr[qmax.peekLast()]<=arr[i]))) {
                    qmax.pollLast();
                }
                qmax.addLast(i);
            }
                
                if((i>(size-1))&&(qmax.peekFirst()<(i-size+1))) {
                    qmax.pop();
                }
                if(i>=size-1) {
                    list.add(arr[qmax.peekFirst()]);
                }
        }
        
     return list;
    }
}

相关文章

网友评论

      本文标题:滑动窗口问题

      本文链接:https://www.haomeiwen.com/subject/ynitwftx.html