leetcode 解题启发 --滑动窗口

阳光穿透心脏的1/2处 2023-05-31 03:16 13阅读 0赞

滑动窗口的应用广泛，常用于减少线性逻辑的时间复杂度问题上。

**滑动窗口思想：在线性逻辑中，允许用单位长度方向性的移动，通过计算窗口的值，求解最终值**

滑动窗口特点：

*  依附于动态规划（大解分为多个小解）
 *  线性移动

滑动窗口思路：

*  确定窗口大小
 *  窗口进出策略
 *  窗口内部逻辑

滑动窗口在定义上更好理解，但是在应用中却更麻烦，窗口移动、进进出出涉及的细节比较多，容易遗漏，下面通过一个直观的例子感受下， leetcode19.删除链表的倒数第N个节点

题目描述：
    
    给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
    
    示例：
    给定一个链表: 1->2->3->4->5, 和 n = 2.
    当删除了倒数第二个节点后，链表变为 1->2->3->5.
    
    说明：
    给定的 n 保证是有效的。

这道题的解决方法可以有多个，这里只说一种双指针法，双指针构成一个滑动窗口，窗口的大小是n，随着窗口移动，第一个指针到达链表末尾时，第二个指针也就到了倒数第n个位置

public class Solution {
        public ListNode remove(ListNode head, int n) {
            //待返回链表
            ListNode dummy = new ListNode(0);
            dummy.next = head;
            //双指针
            ListNode fast = head;
            ListNode slow = dummy;
            //滑动窗口长度
            for (int i = 0; i < n; i++) {
                fast = fast.next;
            }
            //窗口移动
            while (fast != null) {
                fast = fast.next;
                slow = slow.next;
            }
            //删除倒数第n个元素
            slow.next = slow.next.next;
            return dummy.next;
        }
    }

上面的例子直接采用滑动窗口机制，不涉及太多的逻辑，下面看看这道题239.滑动窗口的最大值

题目描述：
    
    给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口 k 内的数字。滑动窗口每次只向右移动一位。
    
    返回滑动窗口最大值。
    
    示例:
    
    输入: 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
    
    注意：
    
    你可以假设 k 总是有效的，1 ≤ k ≤ 输入数组的大小，且输入数组不为空。

代码在下边，先说说思路，根据题目的条件，滑动窗口的大小是k，返回数组，所以看代码的时候，先把跟滑动窗口无关的剔除掉，关注滑动窗口内部逻辑，这里用了双端队列，一个进一个出，用双端队列表示滑动窗口，但只保留最大值

public int[] maxWindow(int[] nums, int k) {
        //异常情况
        if (nums == null || nums.length == 0 || k > nums.length) {
            return new int[0];
        }
        //初始化结果数组
        int[] res = new int[nums.length - k + 1];
        //这里是一个双端队列，保存窗口移动时，最大值的数组下标
        LinkedList<Integer> queue = new LinkedList<>();
        //这个循环表示创建滑动窗口
        for (int i = 0; i < k - 1; i++) {
            //计算滑动窗口的最大值，只保留一个，这里是滑动窗口最开始的地方
            while (!queue.isEmpty() && nums[queue.peekLast()] < nums[i]) {
                queue.pollLast();
            }
            queue.offerLast(i);
        }
        //接着就是遍历了，每滑动一位，找出最大值
        for (int i = k - 1; i < nums.length; i++) {
            while (!queue.isEmpty() && nums[queue.peekLast()] < nums[i]) {
                queue.pollLast();
            }
            queue.offerLast(i);
            //如果窗口超过k了，窗口之前的值不参与计算最大值
            if (i - queue.peekFirst() >= k) {
                queue.pollFirst();
            }
            //保存每个窗口的最大值
            res[i - k + 1] = nums[queue.peekFirst()];
        }
        return res;
    }

滑动窗口思路也适用于leetcode其他题的求解思路：

*  42.接雨水
 *  84.柱状图中最大的矩形
 *  85.最大矩形
 *  141.环形链表
 *  221.最大正方形
 *  438.找到字符串中所有字母异位词