滑动窗口的最大值

public ArrayList<Integer> maxInWindows (int[] num, int size) {
        ArrayList<Integer> r = new ArrayList<>();
        if(num.length < size || size == 0) return r;
        int max = Integer.MIN_VALUE;
        for(int i=0;i<num.length-size+1;i++){
            if(max == Integer.MIN_VALUE){
                for(int j=0;j<size;j++){
                    if(max < num[i+j]) max = num[i+j];
                }
            }else if(max < num[i+size-1]){
                max = num[i+size-1];
            }
            r.add(max);
            if(num[i] == max) max = Integer.MIN_VALUE;
        }
        return r;
    }

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
        // 核心思想：设置一个【单调双端队列】，确保队头是当前窗口内的最大值

        // 0.判断特殊情况
        ArrayList<Integer> result = new ArrayList<>();
        if (size <= 0 || size > num.length) {
            return result;
        }

        // 1.创建双端队列
        Deque<Integer> dq = new LinkedList<>();

        // 2.录入初始窗口
        int h = 0;
        int t = size - 1;
        for (int i = h; i <= t; i++) {
            // 录入的是下标
            inDequeue(num, i, dq);
        }

        // 3.得到初始窗口的结果
        // 注意！从队列中取出来的是下标值，要转换成元素值存入结果中
        result.add(num[dq.peekFirst()]);

        // 4.模拟窗口移动-h右移且t右移，不断得到结果
        for (int i = 1; i <= (num.length - size); i++) {
            // 4.1 t后移，新元素入队
            inDequeue(num, ++t, dq);
            // 4.2 h后移，旧元素出队
            outDequeue(num, h++, dq);
            // 4.3 新窗口形成，从队头获得当前窗口最大元素
            // 注意！从队列中取出来的是下标值，要转换成元素值存入结果中
            result.add(num[dq.peekFirst()]);
        }

        return result;
    }

    // 新元素入单调双端队列的操作
    public void inDequeue(int[] num, int i, Deque<Integer> dq) {
        // 录入的是下标
        if (dq.isEmpty()) {
            // 若队列为空，则直接录入
            dq.addLast(i);
        }
        else if (num[i] < num[dq.peekLast()]) {
            // 若待录入元素小于队尾元素，则入队
            dq.addLast(i);
        } else {
            // 若待录入元素大于等于队尾元素，则不断地让堆尾元素出队，直到满足小于队尾元素入队
            // 等于也要出队的目的是让新的元素替代队列中旧的元素
            while (!dq.isEmpty() && num[i] >= num[dq.peekLast()]) {
                dq.pollLast();
            }
            // 此时队列空了，或者队尾下标元素大于当前待入队元素
            dq.addLast(i);
        }
    }

    // 旧元素出单调双端队列的操作
    public void outDequeue(int[] num, int i, Deque<Integer> dq) {
        // 录入的是下标
        if (i == dq.peekFirst()) {
            // 当待出队元素正好是队头元素（当前窗口最大）时才出队
            dq.pollFirst();
        }
        // 当待出队元素不是队头元素（当前窗口最大）时不用出队
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param num int整型一维数组
     * @param size int整型
     * @return int整型ArrayList
     */
    public ArrayList<Integer> maxInWindows (int[] num, int size) {
        int n = num.length;
        if (size == 0 || size > n) {
            return new ArrayList<Integer>();
        }
        PriorityQueue<Integer> q = new PriorityQueue<>((a, b)-> {
            return b - a;
        });
        ArrayList<Integer> res = new ArrayList<>();

        int i = 0;
        for (int j = 0; j < n; j++) {
            q.add(num[j]);
            if (j - i + 1 == size) {
                res.add(q.peek());
            }
            if (j - i + 1 == size) {
                q.remove(num[i]);
                i++;
            }
        }
        return res;
    }
}

模板题hh

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;
        // 队列存的索引，用以方便最大值滑出窗口
        int[] q = new int[10010];
        int hh = 0, tt = -1;
        // 枚举窗口右端点
        for (int i = 0; i < num.length; i++) {
            // 维护单调队列 最值可能已滑出窗口，基于索引，如果最值索引和右端点算出的窗口大小超过 size 那就说明最值索引已经出窗口了，需要剔除
            while (hh <= tt && i - q[hh] + 1 > size) hh++;
            // 将新入元素维护到单调队列中 (第一个比它大的元素之后，注意队列维护索引值！)
            while (hh <= tt && num[q[tt]] <= num[i]) tt--;
            q[++tt] = i;
            // 枚举到窗口大小时，开始收集最值
            if (i + 1 >= size) res.add(num[q[hh]]);
        }
        return res;
    }
}

//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;
    }
}