给定一个有序数组arr，代表坐落在X轴上的点给定一个正数K，代表绳子的长度返回绳子最多压中几个点？即使绳子边缘处盖住点也算盖住

拼搏现实的明天。 2024-03-29 15:11 51阅读 0赞

#### 目录 ####

*   *  题目描述
     *  暴力求解
     *  贪心+二分法
     *  滑动窗口
     *  对数器测试

### 题目描述 ###

> 给定一个有序数组arr，代表坐落在X轴上的点  
> 给定一个正数K，代表绳子的长度  
> 返回绳子最多压中几个点？  
> 即使绳子边缘处盖住点也算盖住

这道题有三个解决方案

### 暴力求解 ###

//暴力求解O(N^2)
        public static int test(int[] arr, int L) {
        
            int max = 0;
            for (int i = 0; i < arr.length; i++) {
        
                int pre = i - 1;
                while (pre >= 0 && arr[i] - arr[pre] <= L) {
        
                    pre--;
                }
                max = Math.max(max, i - pre);
            }
            return max;
        }

### 贪心+二分法 ###

贪心体现在每次都拿绳子的尾部压住数组上存在的点。  
当前位置的值减去绳子长度就是当前位置所能压到的最远的点。  
使用二分查找寻找这个位置。  
例如当前位置的值为893，绳子长度为100，当前位置能压到的最远位置为793。  
使用二分查找寻找值为793的下标位置（如果不存在这个值，那么就找最小的大于793的值的位置）。  
时间复杂度：O(N \* log N)

//贪心+二分法O(N*logN)
        public static int maxPoint1(int[] arr, int L) {
        
            int res = 1;
            for (int i = 0; i < arr.length; i++) {
        
                int nearest = nearestIndex(arr, i, arr[i] - L);
                res = Math.max(res, i - nearest + 1);
            }
            return res;
        }
    
        public static int nearestIndex(int[] arr, int R, int value) {
        
            int L = 0;
            int index = R;
            while (L <= R) {
        
                int mid = L + ((R - L) >> 1);
                if (arr[mid] >= value) {
        
                    index = mid;
                    R = mid - 1;
                } else {
        
                    L = mid + 1;
                }
            }
            return index;
        }

### 滑动窗口 ###

left和right不会退  
![在这里插入图片描述][52aaa7d0ba334cf1b94f66d3887de8ab.png]  
![在这里插入图片描述][95b3d73dc328427a8d4f949e1736f2d2.png]  
![在这里插入图片描述][1dceeb3c06a842378bbf4674302662e2.png]

### 对数器测试 ###

public class CordCoverMaxPoint {
        
    
        //贪心+二分法O(N*logN)
        public static int maxPoint1(int[] arr, int L) {
        
            int res = 1;
            for (int i = 0; i < arr.length; i++) {
        
                int nearest = nearestIndex(arr, i, arr[i] - L);
                res = Math.max(res, i - nearest + 1);
            }
            return res;
        }
    
        public static int nearestIndex(int[] arr, int R, int value) {
        
            int L = 0;
            int index = R;
            while (L <= R) {
        
                int mid = L + ((R - L) >> 1);
                if (arr[mid] >= value) {
        
                    index = mid;
                    R = mid - 1;
                } else {
        
                    L = mid + 1;
                }
            }
            return index;
        }
    
        //滑动窗口O(N)
        public static int maxPoint2(int[] arr, int L) {
        
            int left = 0;
            int right = 0;
            int N = arr.length;
            int max = 0;
            while (left < N) {
        
                while (right < N && arr[right] - arr[left] <= L) {
        
                    right++;
                }
                max = Math.max(max, right - (left++));
            }
            return max;
        }
    
        //暴力求解O(N^2)
        public static int test(int[] arr, int L) {
        
            int max = 0;
            for (int i = 0; i < arr.length; i++) {
        
                int pre = i - 1;
                while (pre >= 0 && arr[i] - arr[pre] <= L) {
        
                    pre--;
                }
                max = Math.max(max, i - pre);
            }
            return max;
        }
    
        // for test
        public static int[] generateArray(int len, int max) {
        
            int[] ans = new int[(int) (Math.random() * len) + 1];
            for (int i = 0; i < ans.length; i++) {
        
                ans[i] = (int) (Math.random() * max);
            }
            Arrays.sort(ans);
            return ans;
        }
    
        public static void main(String[] args) {
        
            int len = 100;
            int max = 1000;
            int testTime = 100000;
            System.out.println("测试开始");
            for (int i = 0; i < testTime; i++) {
        
                int L = (int) (Math.random() * max);
                int[] arr = generateArray(len, max);
                int ans1 = maxPoint1(arr, L);
                int ans2 = maxPoint2(arr, L);
                int ans3 = test(arr, L);
                if (ans1 != ans2 || ans2 != ans3) {
        
                    System.out.println("oops!");
                    break;
                }
            }
    
        }
    
    }

[52aaa7d0ba334cf1b94f66d3887de8ab.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/ebaaffe04f79490a93a690f23d8c0f31.png
[95b3d73dc328427a8d4f949e1736f2d2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/7bff1594772a44a38890917329e0ecde.png
[1dceeb3c06a842378bbf4674302662e2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/9957fe77e61e473fb7a2348298ff7eb9.png