绳子最大覆盖点数【窗口】

冷不防 2024-05-25 17:34 176阅读 0赞

### 文章目录  @\[TOC\]  前言  一 题目描述  二 题解  1. 二分查找  1.1 思路  1.2 代码示例  2. 双指针(窗口)  2.1 思路  2.2 代码示例  三:总结 ###

## 前言 ##

大厂经典算法题-基础篇，主要是作者在准备各大大厂笔试面试中遇到的经典且难度属于simple-mid 难度的题目，准备大厂面试算法是一个需要长期积累的过程，希望大家都能够坚持下来，在此和大家共勉！

--------------------

## 一 题目描述 ##

`给定一个有序数组arr，arr中的每个值代表坐落在x轴上的点，再给定一个正整数K，表示一根绳子的长度，绳子可以任意放在x轴上，请返回绳子最多能盖住多少个点。注意绳子的边缘盖住也算作盖住。`

--------------------

## 二 题解 ##

?:思路  
`我们可以尝试以arr中的每一个点左为绳子的起点，然后把绳子拉直，看看绳子能盖住几个点，这样我们遍历一次arr，尝试以每一个点作为起点看绳子最多能盖住多少个点，每一个点都会有一个局部最优解，然后所有局部最优解中的max，就是绳子最多能盖住的点数。`

❓：**现在我们只需要去考虑在每一个点做绳子起点的时候，如何考虑统计绳子盖住的点数。**

要解决上述问题，我提供了两种解法

--------------------

### 1. 二分查找 ###

#### 1.1 思路 ####

**`思路:不妨设数组arr的长度为N，现在尝试以L号下标作为绳子的左边界，那么我们只需要求在arr[L.....N-1]范围内小于等于arr[L]+k 最右位置的下标R，那么R-L+1,就是尝试这个L下标的绳子覆盖点数。`**

> **题眼:利用二分找小于等于arr\[L\]+k的最右侧的节点**

#### 1.2 代码示例 ####

public static int maxCoverPoint(int[] arr,int K){
        
            if (arr == null || arr.length == 0 || K <= 0) {
        
                return 0;
            }
            int max=1;
            for(int L=0;L<arr.length;L++){
        
                int R=binarySearch(arr,L,K);
                max=Math.max(max,R-L+1);
            }
            return max;
        }
        public static int binarySearch(int[] arr,int i,int K){
        
            int L=i;
            int R=arr.length-1;
            int target=arr[i]+K;
            int ans=-1;
            while(L<=R){
        
                //1:找中点
                int mid=L+((R-L)>>1);
                if(arr[mid]<=target){
        
                    ans=mid;
                    L=mid+1;
                }
                else{
        
                    R=mid-1;
                }
            }
            return ans;
        }

--------------------

### 2. 双指针(窗口) ###

#### 2.1 思路 ####

> **`?：如果arr[R]-arr[L]<=k,时让R向右移动，直到不满足条件时，R-L就是尝试以L位置作为绳子左边界时绳子覆盖的点数。`**  
> **?：窗口问题的关键点就是证明双指针不回退，如果指针回退则用窗口完全达不到加速的效果。**  
> **1. 因为绳子的长度是固定为k，且数组arr是有序的。如果我们把R不断右移直到第一次满足arr\[R\]-arr\[L\]>k时，这个R位置就是以L作为绳子的左边界第一次覆盖不到的点，又数组有序，固R及其右边的所有点，一定有arr\[R\]-arr\[L\]>k,因此我们不需要考虑R及其以后的点被覆盖的情况。  
> 2. 如果我们尝试（L+1）号位置时，绳子的长度是固定为k，所以我们每必要回退R，只需要在R上次失败的位置继续向后比配就行了。**

#### 2.2 代码示例 ####

public static int maxCoverPoint(int[] arr, int K) {
        
            //双指针 时间复杂度为O(N)
            if (arr == null || arr.length == 0 || K <= 0) {
        
                return 0;
            }
            int max=1;
            int L=0;
            int R=0;
            for(;L<arr.length;L++){
        
                while(R<arr.length&&arr[R]-arr[L]<=K){
        
                    R++;
                }
                //R指向的是匹配失败的位置
                max=Math.max(max,R-L);
            }
            return max;
        }

--------------------

## 三:总结 ##

> **这题是窗口问题中的经典题目，窗口模型的关键之处在于双指针不回退，每次尝试下一个开头的时候，都只需要从上一个失败的位置继续尝试即可，而不需要回退R指针。**

**`本题的双指针代码可以作为窗口模型的模板代码，这是必须要掌握的模板。`**