滑动窗口的最大值

//java双指针解法
import java.util.*;


public class Solution {
    public ArrayList<Integer> maxInWindows (int[] num, int size) {
        //定义内指针
        int i = 0;
        //定义外指针
        int j = 0;
        //记录最大值
        int max = 0;
        //初始化ArrayList来储存结果
        ArrayList<Integer> arr  = new ArrayList<>();
        //如果数组长度小于size或者size为0返回空
        if (num.length<size||size==0) return arr;
        //外指针需要遍历的次数为数组长度-size+1
        for (int index = 0;index< num.length-size+1;index++) {
            //每次将最大值初始化为当前滑块的第一个值
            max = num[i];
            //内循环，遍历滑块中的每一个数
            while (i<size+j-1){
                i++;
                //找到最大值
                if (max<num[i]){
                    max = num[i];
                }
            }
            //遍历完成后外循环指针加1
            j++;
            //将最大值添加到结果中
            arr.add(max);
            //每次循环完成一个滑块后将内指针i的位置移到下一个滑块的第一个位置上
            i = j;
        }
        return arr;
    }
}

public class Solution {
    /**
     * 给定一个长度为 n 的数组 num 和滑动窗口的大小 size ，找出所有滑动窗口里数值的最大值。
     *
     * 双端队列保存最大值的下标
     *
     * @param num int整型一维数组
     * @param size int整型
     * @return int整型ArrayList
     */
    public ArrayList<Integer> maxInWindows (int[] num, int size) {
        ArrayList<Integer> result = new ArrayList<>();
        if (size > num.length || size == 0) {
            return result;
        }
        ArrayDeque<Integer> que = new ArrayDeque<>();
        que.offerFirst(0);
        for (int i = 0; i < num.length; i++) {
            //当前元素比头更大，队列清空，保存下标
            if (num[i] >= num[que.peekFirst()]) {
                que.clear();
                que.offerFirst(i);
            }
            //比头小，也比尾小，下标置尾
            else if (num[i] < num[que.peekLast()]) {
                que.offerLast(i);
            }
            //比头小，比尾大，删除原来的尾部，再下标置尾
            else {
                que.pollLast();
                que.offerLast(i);
            }
            //检查下标元素是否在窗口，不在，则头部下标移除
            if (que.peekFirst() <= i - size) {
                que.pollFirst();
            }
            //窗口饱和开始记录最大值
            if (i >= size - 1) {
                result.add(num[que.peekFirst()]);
            }
        }
        return result;
    }

}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param num int整型一维数组
     * @param size int整型
     * @return int整型ArrayList
     */
    public ArrayList<Integer> maxInWindows (int[] num, int size) {
        int i = 0;
        int j = i + size - 1;
        int preMaxIndex = -1, maxIndex = -1;
        int preMax = Integer.MIN_VALUE, max = Integer.MAX_VALUE;
        ArrayList<Integer> arrayList = new ArrayList<>();
        for (int index = i; index <= j && j < num.length; index++) {
            if (maxIndex >= i && maxIndex <= j) {
                if (num[j] > max) {
                    max = num[j];
                    maxIndex = j;
                }
                arrayList.add(max);
                index = ++i - 1;
                j++;
                continue;
            } else if ((maxIndex < i || maxIndex > j) && index == i) {
                preMax = Integer.MIN_VALUE;
            }
            if (preMax < num[index]) {
                preMax = num[index];
                preMaxIndex = index;
            }
            if (index == j) {
                max = preMax;
                maxIndex = preMaxIndex;
                arrayList.add(max);
                index = ++i - 1;
                j++;
            }
        }
        return arrayList;
    }
}

public static ArrayList<Integer> maxInWindows(int[] num, int size) {
        int left = 0;
        int right = size - 1;
        ArrayList<Integer> temp = new ArrayList<>();
        ArrayList<Integer> ret = new ArrayList<>();
        while (right < num.length) {
            for (int i = 0; i < size; i++) {
                temp.add(num[left]);
                left++;
                right++;
            }
            Optional<Integer> max = temp.stream().max(Integer::compareTo);
            max.ifPresent(ret::add);
            left = left - size + 1;
            right = right - size + 1;
            temp = new ArrayList<>();
        }
        return ret;
    }

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型一维数组 
     * @param size int整型 
     * @return int整型ArrayList
     */
    public ArrayList<Integer> maxInWindows (int[] nums, int k) {
        // 1. 参数判断
        if(k <= 0) {
            return new ArrayList<>();
        }
        if(nums.length < k) {
            return new ArrayList<>();
        }
        // 2. 创建滑动窗口最大值的数组
        // 长度为 nums.length - k + 1
        ArrayList<Integer> ans = new ArrayList<>();

        // 3. 定义左右窗口
        int L = 0;// 左窗口
        int R = 0;// 右窗口

        // 4. 创建双端队列来保存区间内的最大值
        LinkedList<Integer> queue = new LinkedList<>();

        // 5. 右窗口往右移动,添加元素
        for(R = 0;R < nums.length;R++) {
            // 6. 如果双端队列没有元素,直接添加
            // 如果双端队列有元素,还要判断队尾的值是否小于等于滑动窗口右侧的值,因为我们要保证双端队列要从大到小排列
            while(!queue.isEmpty() && nums[queue.peekLast()] <= nums[R]) {
                queue.pollLast();
            }

            // 7. 添加元素到双端队列
            // 注意:添加到双端队列的是对应的下标
            queue.addLast(R);

            // 8. 更新双端队列头部的值
            if(queue.peekFirst() == R - k) {
                queue.pollFirst();
            }

            // 9. 添加结果到答案数组中
            // 当 R 来到了第三个位置的时候,就形成了长度为 3 的滑动窗口,此时就可以记录最大值了
            if(R >= k - 1) {
                ans.add(nums[queue.peekFirst()]);
            }
        }

        return ans;
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param num int整型一维数组
     * @param size int整型
     * @return int整型ArrayList
     */
    public ArrayList<Integer> maxInWindows (int[] num, int size) {
        // write code here
        ArrayList<Integer> res = new ArrayList<Integer>();
        if (size > num.length || size == 0) return res;
        for (int i = 0; i <= num.length - size; i++) {
            Stack<Integer> max = new Stack<Integer>();
            for (int j = i; j  < i + size; j++) {
                int temp = num[j];
                if (max.isEmpty() || (max.peek() < num[j])) {
                    max.push(num[j]);
                } else {
                    max.push(max.peek());
                }
            }
            res.add(max.peek());
        }
        return res;
    }
}

public ArrayList<Integer> maxInWindows (int[] num, int size) {
       
        // A进入窗口时，依次从尾部排除掉小于A的值
        // 窗口每次移动，从队首弹出窗口最前面的值
        //即将进入的值>窗口末尾值  那就一直弹出窗口末尾值，再加进去
        //当前窗口大于窗口距离，弹出队首
        //养窗口，当i>size，先在ans中放队列的队首值
        //队首始终是最大值
        Deque<Integer> qu=new LinkedList<>();//存的是索引下标
        ArrayList<Integer> ans=new ArrayList<>();
         if(num==null||size==0) return ans;
        for(int i=0;i<num.length;i++){//遍历元素中养窗口
        //Last()最后一个元素
        //First()第一个元素
            while(!qu.isEmpty()&&num[i]>num[qu.peekLast()]){//当前值>nums[索引]
                qu.pollLast();  //删掉的都是队尾元素
            }
            while(!qu.isEmpty()&&(i-qu.peekFirst()>=size)){//i-First()算窗口距离  >size，划出队的第一个元素
                qu.pollFirst();//删掉队头元素
            }
            qu.add(i);
            if(i>=size-1){//当i大于当前窗口值  （size-1是因为这里是从i是从0开始计数的）
                ans.add(num[qu.peekFirst()]);  //加入结果集的都是队头元素
            }
        }
        return ans;
    }

import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        if (size > num.length || size == 0) {
            return list;
        }
        for (int i = 0; i <= num.length-size; i++) {
            int[] subArr = Arrays.copyOfRange(num, i, i + size);
            int asInt = Arrays.stream(subArr).max().getAsInt();
            list.add(asInt);
        }
        return list;
    }
}

import java.util.*;
public class Solution {
    //暴力就完事了
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer> arr = new ArrayList<>();
        if(size>num.length||size==0) return arr;
        for(int i=0;i<=num.length-size;i++){
            int max=Integer.MIN_VALUE;
            for(int j=i;j<i+size;j++){
                if(num[j]>max) max=num[j];
            }
            arr.add(max);
        }
        return arr;
    }
}

/*//方法一：暴力破解法
import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer> res = new ArrayList<>();
        if(size==0 || size>num.length){
            return res;
        }
        for(int i=size;i<=num.length;i++){
            int max = find(num,i-size,i);
            res.add(max);
        }
        return res;
    }
    public int find(int[] num, int l, int r){
        int max = num[l];
        for(int i=l;i<r;i++){
            if(max < num[i]){
                max = num[i];
            }
        }
        return max;
    }
}*/

//方法二 双端队列
import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        //窗口长度不符合的情况
        ArrayList<Integer> res = new ArrayList<>();
        if (size == 0 || size > num.length) {
            return res;
        }
        //双端队列 存放数值的下标。当遍历的数值比队列末尾大，则末尾弹出【即在它前面比他小的都无用】，否则放入数值。
        //如果队列开头数值超过了窗口的范围则从头部弹出。并存放进结果集中。
        Deque<Integer> q = new ArrayDeque<>();
        //先遍历第一个窗口
        for (int i = 0; i < size; i++) {
            while (!q.isEmpty() && num[q.peekLast()] < num[i]) {  //前面小的不用保留
                q.pollLast();
            }
            q.add(i);
        }
        //继续遍历
        for (int i = size; i < num.length; i++) {
            //先把队列开头最大值存放进结果集中
            res.add(num[q.peekFirst()]); 
            //判断窗口是否出界
            if (!q.isEmpty() && q.peekFirst() < (i - size + 1)) {
                q.pollFirst();
            }
            //继续往双端队列中存放
            while (!q.isEmpty() && num[q.peekLast()] < num[i]) {
                q.pollLast();
            }
            q.add(i);
        }
        //把最后一个窗口的最大值存放进结果集中
        res.add(num[q.peekFirst()]);
        return res;
    }
}