3112、访问消失节点的最小时间

题目

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

示例 2：

输入：nums = [1], k = 1
输出：[1]

提示：

• $1 <= nums.length <= 10^5#
• $10^4 <= nums[i] <= 10^4$
• 1 <= k <= nums.length

分析

可以采用双指针遍历，更新滑动窗口的最大值：

• 最大值下标，大于left
  • 最右值大于等于窗口最大值，则更新最大值及其下标
• 最右值大于等于窗口最大值 - 1，则更新最大值及其下标
• 最左值大于等于窗口最大值 - 1，则更新最大值及其下标
• 最坏的情况：从left遍历到right，记录最大值及其下标

双指针遍历

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
       int left = 0, right = k - 1;
        int maxindex = -1;
        int max = Integer.MIN_VALUE;
        int[] ans = new int[nums.length - k + 1];
        while (right < nums.length) {// 没超过最大值
            // 巧妙利用if else的分支只选一个执行的特性
            if (left <= maxindex) { // 这种情况，直接根据最右值更新
                if (nums[right] >= max) {
                    max = nums[right];
                    maxindex = right;// 更新最大值下标
                }
            } else if (nums[right] >= max - 1) {// 右侧最大值更新
                max = nums[right];
                maxindex = right;
            } else if (nums[left] >= max - 1) {// 左侧最大值更新
                max = nums[left];
                maxindex = left;
            } else {
                // 最坏的情况，需要扫描一边更新一个最大值
                max = nums[left];
                for (int i = left + 1; i <= right; i++) {
                    if (nums[i] >= max) {
                        max = nums[i];
                        maxindex = i;
                    }
                }
            }
            ans[left] = max;
            left++;
            right++;
        }
        return ans;
    }
}

优先队列维护最大值

优先队列存储k个元素，维护最大值。更新窗口，然后自动更新最大值。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        // 优先队列，内部元素是长度为2的数组，第一个是值 第二个是下标
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] pair1, int[] pair2) {
                return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];
            }
        });
        // 放入k个元素
        for (int i = 0; i < k; ++i) {
            pq.offer(new int[]{nums[i], i});
        }
        int[] ans = new int[n - k + 1];
        ans[0] = pq.peek()[0];
        for (int i = k; i < n; ++i) {
            pq.offer(new int[]{nums[i], i});
            while (pq.peek()[1] <= i - k) {
                pq.poll();
            }
            ans[i - k + 1] = pq.peek()[0];// 更新最大值数组
        }
        return ans;
    }
}

单调队列

采用一个单调递减队列，维护最大值下标

class Solution {
    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()];// 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;
    }
}

分块 + 预处理

稀疏表思想

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] prefixMax = new int[n];// 后缀最大值数组
        int[] suffixMax = new int[n];// 前缀最大值数组
        for (int i = 0; i < n; ++i) {
            if (i % k == 0) {// 块的边缘，直接赋值
                prefixMax[i] = nums[i];
            } else {
                prefixMax[i] = Math.max(prefixMax[i - 1], nums[i]);
            }
        }
        for (int i = n - 1; i >= 0; --i) {
            if (i == n - 1 || (i + 1) % k == 0) {// 块的边缘，直接赋值
                suffixMax[i] = nums[i];
            } else {
                suffixMax[i] = Math.max(suffixMax[i + 1], nums[i]);
            }
        }

        // 遍历最大最小前缀数组
        int[] ans = new int[n - k + 1];
        for (int i = 0; i <= n - k; ++i) {
            ans[i] = Math.max(suffixMax[i], prefixMax[i + k - 1]);
        }
        return ans;
    }
}

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com