239. 滑动窗口最大值

最初想法：用hashmap记录窗口中出现的数字的个数，maxNum记录当前窗口的最大数，当窗口滑动后左侧数个数减一，右侧数个数加一，同时查看原最大数的个数是否为0，如果为0：遍历当前hashmap中的key找到最大的，如果不为0：将新加入的数与原最大数比较，但是timeout了

    public int[] maxSlidingWindow(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int[] res = new int[nums.length - k + 1];
        int[] maxNum = {-1000005};
        for(int i = 0; i < k; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
            if(nums[i] > maxNum[0]) {
                maxNum[0] = nums[i];
            }
        }
        res[0] = maxNum[0];
        for(int begin = 0, end = k; end < nums.length; begin++, end++) {
            map.put(nums[begin], map.getOrDefault(nums[begin], 0) - 1);
            map.put(nums[end], map.getOrDefault(nums[end], 0) + 1);
            if(map.get(maxNum[0]) == 0) {
                maxNum[0] = -1000005;
                map.entrySet().forEach(entry -> {
                    if(entry.getValue() > 0) {
                        if(entry.getKey() > maxNum[0]) maxNum[0] = entry.getKey();
                    }
                });
            } else {
                if(nums[end] > maxNum[0]) {
                    maxNum[0] = nums[end];
                }
            }
            res[begin + 1] = maxNum[0];
        }
        return res;
    }

上面之所以超时是因为我们在维护窗口内的最大数的时间开销太大了，于是我就想如果能以较小的开销找到最大的数说不定就不会超时了，所以想到了treemap，TreeMap是有序的，内部维护了键的排序顺序 解决了重新找最大键的过于耗时的问题。

    public int[] maxSlidingWindow(int[] nums, int k) {
       TreeMap<Integer, Integer> map = new TreeMap<>();
        int[] res = new int[nums.length - k + 1];
        int maxNum = -1000005;
        for(int i = 0; i < k; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
            if(nums[i] > maxNum) {
                maxNum = nums[i];
            }
        }
        res[0] = maxNum;
        for(int begin = 0, end = k; end < nums.length; begin++, end++) {
            if (map.getOrDefault(nums[begin], 0) - 1 > 0) {
                map.put(nums[begin], map.getOrDefault(nums[begin], 0) - 1);
            } else {
                map.remove(nums[begin]);
            }
            map.put(nums[end], map.getOrDefault(nums[end], 0) + 1);
            if(map.getOrDefault(maxNum, 0) == 0) {
                maxNum = map.lastKey();
            } else {
                if(nums[end] > maxNum) {
                    maxNum = nums[end];
                }
            }
            res[begin + 1] = maxNum;
        }
        return res;
    }

后面我又想如果把查找时间压缩到log n级别行不行，也就是用二分找

呵结果还是T了（哭）

    public static int binarySearch(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] < target) {
                right = mid - 1;
            }
            if (nums[mid] > target) {
                left = mid + 1;
            }
        }
        return -1;
    }

    //二分删除的实现
    public static void binaryDelete(int[] array, int value, int size) {
        int index = binarySearch(array, value);
        for (int i = index; i < size - 1; i++) {
            array[i] = array[i + 1];
        }
        array[size - 1] = -1000005;
    }

    // 二分插入实现
    public static void binaryInsert(int[] array, int value, int size) {
        int index = findInsertionIndex(array, value);
        for(int i = size - 1; i > index; i--) {
            array[i] = array[i - 1];
        }
        array[index] = value;
    }

    // 查找插入位置的实现
    private static int findInsertionIndex(int[] array, int value) {
        int left = 0;
        int right = array.length;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (array[mid] < value) {
                right = mid; // 插入位置在左半部分
            } else {
                left = mid + 1; // 插入位置在右半部分
            }
        }
        return left; // 返回插入位置
    }

    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] ans = new int[nums.length - k + 1];
        int[] window = new int[k];//窗口内数的非递增排序
        for (int i = 0; i < k; i++) {
            window[i] = -1000005;
        }
        for(int i = 0; i < k; i++) {
            binaryInsert(window, nums[i], i + 1);
        }
        ans[0] = window[0];
        for(int begin = 0, end = k; end < nums.length; begin++, end++) {
            binaryDelete(window, nums[begin], k);
            binaryInsert(window, nums[end], k);
            ans[begin + 1] = window[0];
        }
        return ans;
    }

因为TreeMap的那个做法花费的时间是500多嘛，就又学习了一下大佬的题解写了这个用单调队列的做法

    //单调队列
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length; // 数组的长度
        Deque<Integer> deque = new LinkedList<Integer>(); // 双端队列，用于存储索引

        // 处理第一个窗口
        for (int i = 0; i < k; ++i) {
            // 维护队列的单调性，保持队列中从大到小的顺序
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast(); // 移除队尾元素，确保队列中的元素从大到小排列
            }
            deque.offerLast(i); // 将当前索引加入队列
        }

        int[] ans = new int[n - k + 1]; // 结果数组
        ans[0] = nums[deque.peekFirst()]; // 第一个窗口的最大值

        // 处理后续的窗口
        for (int i = k; i < n; ++i) {
            // 维护队列的单调性
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast(); // 移除队尾元素，确保队列中的元素从大到小排列
            }
            deque.offerLast(i); // 将当前索引加入队列

            // 移除超出窗口范围的元素
            while (deque.peekFirst() <= i - k) {
                deque.pollFirst(); // 移除队头元素，确保队列中的索引在窗口范围内
            }

            ans[i - k + 1] = nums[deque.peekFirst()]; // 当前窗口的最大值
        }

        return ans; // 返回结果数组
    }