Medium

题目描述

给你一个二维整数数组 tiles ，其中 tiles[i] = [li, ri] ，表示所有在 li <= j <= ri 范围内的瓷砖 j 都被涂成了白色。

同时给你一个整数 carpetLen ，表示可以放在任何地方的一块地毯的长度。

请你返回地毯能覆盖的最多白色瓷砖数。

示例 1：

输入：tiles = [[1,5],[10,11],[12,18],[20,25],[30,32]], carpetLen = 10
输出：9
解释：将地毯放在瓷砖 10 上。
地毯覆盖 9 块白色瓷砖，所以我们返回 9 。
注意可能有其他地方放置地毯也会覆盖 9 块瓷砖。
可以证明地毯无法覆盖超过 9 块瓷砖。

示例 2：

输入：tiles = [[1,1],[10,11]], carpetLen = 2
输出：2
解释：将地毯放在瓷砖 10 上。
地毯覆盖 2 块白色瓷砖，所以我们返回 2 。

提示：

  • 1 <= tiles.length <= 5 * 10^4
  • tiles[i].length == 2
  • 1 <= li <= ri <= 10^9
  • 1 <= carpetLen <= 10^9
  • 瓷砖互不重叠。

解题思路

解题思路

这道题的核心思想是滑动窗口结合前缀和优化。

分析过程：

  1. 观察最优解性质：最优的地毯放置位置一定是从某个瓷砖区间的起点开始，因为如果地毯的起点在空隙中，我们总能向左移动地毯来覆盖更多瓷砖。

  2. 暴力思路：枚举每个可能的起点位置，计算从该点开始长度为 carpetLen 的地毯能覆盖多少瓷砖。但直接计算会超时。

  3. 滑动窗口优化：

    • 先将瓷砖区间按起点排序
    • 使用双指针维护一个窗口，窗口内的所有瓷砖区间都与当前地毯位置有交集
    • 当移动地毯起点时，动态维护窗口边界

  4. 前缀和加速：

    • 预计算每个瓷砖区间的长度前缀和
    • 窗口内完全被覆盖的区间可以通过前缀和快速计算
    • 只需单独处理窗口右边界可能部分覆盖的区间

算法流程：

  1. 排序瓷砖区间
  2. 计算前缀和数组
  3. 枚举每个区间起点作为地毯起点
  4. 使用双指针维护有效窗口
  5. 快速计算当前窗口覆盖的瓷砖数

推荐解法：滑动窗口 + 前缀和，时间复杂度最优。

代码实现

class Solution {
public:
    int maximumWhiteTiles(vector<vector<int>>& tiles, int carpetLen) {
        sort(tiles.begin(), tiles.end());
        
        int n = tiles.size();
        vector<long long> prefixSum(n + 1, 0);
        
        // 计算每个区间长度的前缀和
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + (tiles[i][1] - tiles[i][0] + 1);
        }
        
        int maxCovered = 0;
        int right = 0;
        
        for (int left = 0; left < n; left++) {
            int carpetStart = tiles[left][0];
            int carpetEnd = carpetStart + carpetLen - 1;
            
            // 移动右指针，找到地毯覆盖范围内的所有区间
            while (right < n && tiles[right][0] <= carpetEnd) {
                right++;
            }
            
            // 计算完全覆盖的区间数量
            int covered = 0;
            if (right > left) {
                // 完全覆盖的区间：[left, right-2]
                if (right - 1 > left) {
                    covered += prefixSum[right - 1] - prefixSum[left];
                }
                
                // 检查最后一个区间是否部分覆盖
                int lastIdx = right - 1;
                if (tiles[lastIdx][0] <= carpetEnd) {
                    int partialCover = min(tiles[lastIdx][1], carpetEnd) - tiles[lastIdx][0] + 1;
                    covered += partialCover;
                }
            }
            
            maxCovered = max(maxCovered, covered);
        }
        
        return maxCovered;
    }
};

class Solution:
    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:
        tiles.sort()
        n = len(tiles)
        
        # 计算每个区间长度的前缀和
        prefix_sum = [0] * (n + 1)
        for i in range(n):
            prefix_sum[i + 1] = prefix_sum[i] + (tiles[i][1] - tiles[i][0] + 1)
        
        max_covered = 0
        right = 0
        
        for left in range(n):
            carpet_start = tiles[left][0]
            carpet_end = carpet_start + carpetLen - 1
            
            # 移动右指针，找到地毯覆盖范围内的所有区间
            while right < n and tiles[right][0] <= carpet_end:
                right += 1
            
            # 计算覆盖的瓷砖数
            covered = 0
            if right > left:
                # 完全覆盖的区间：[left, right-2]
                if right - 1 > left:
                    covered += prefix_sum[right - 1] - prefix_sum[left]
                
                # 检查最后一个区间是否部分覆盖
                last_idx = right - 1
                if tiles[last_idx][0] <= carpet_end:
                    partial_cover = min(tiles[last_idx][1], carpet_end) - tiles[last_idx][0] + 1
                    covered += partial_cover
            
            max_covered = max(max_covered, covered)
        
        return max_covered

public class Solution {
    public int MaximumWhiteTiles(int[][] tiles, int carpetLen) {
        Array.Sort(tiles, (a, b) => a[0].CompareTo(b[0]));
        
        int n = tiles.Length;
        long[] prefixSum = new long[n + 1];
        
        // 计算每个区间长度的前缀和
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + (tiles[i][1] - tiles[i][0] + 1);
        }
        
        int maxCovered = 0;
        int right = 0;
        
        for (int left = 0; left < n; left++) {
            int carpetStart = tiles[left][0];
            int carpetEnd = carpetStart + carpetLen - 1;
            
            // 移动右指针，找到地毯覆盖范围内的所有区间
            while (right < n && tiles[right][0] <= carpetEnd) {
                right++;
            }
            
            // 计算覆盖的瓷砖数
            int covered = 0;
            if (right > left) {
                // 完全覆盖的区间：[left, right-2]
                if (right - 1 > left) {
                    covered += (int)(prefixSum[right - 1] - prefixSum[left]);
                }
                
                // 检查最后一个区间是否部分覆盖
                int lastIdx = right - 1;
                if (tiles[lastIdx][0] <= carpetEnd) {
                    int partialCover = Math.Min(tiles[lastIdx][1], carpetEnd) - tiles[lastIdx][0] + 1;
                    covered += partialCover;
                }
            }
            
            maxCovered = Math.Max(maxCovered, covered);
        }
        
        return maxCovered;
    }
}

var maximumWhiteTiles = function(tiles, carpetLen) {
    tiles.sort((a, b) => a[0] - b[0]);
    
    const n = tiles.length;
    const prefixSum = new Array(n + 1).fill(0);
    
    // 计算每个区间长度的前缀和
    for (let i = 0; i < n; i++) {
        prefixSum[i + 1] = prefixSum[i] + (tiles[i][1] - tiles[i][0] + 1);
    }
    
    let maxCovered = 0;
    let right = 0;
    
    for (let left = 0; left < n; left++) {
        const carpetStart = tiles[left][0];
        const carpetEnd = carpetStart + carpetLen - 1;
        
        // 移动右指针，找到地毯覆盖范围内的所有区间
        while (right < n && tiles[right][0] <= carpetEnd) {
            right++;
        }
        
        // 计算覆盖的瓷砖数
        let covered = 0;
        if (right > left) {
            // 完全覆盖的区间：[left, right-2]
            if (right - 1 > left) {
                covered += prefixSum[right - 1] - prefixSum[left];
            }
            
            // 检查最后一个区间是否部分覆盖
            const lastIdx = right - 1;
            if (tiles[lastIdx][0] <= carpetEnd) {
                const partialCover = Math.min(tiles[lastIdx][1], carpetEnd) - tiles[lastIdx][0] + 1;
                covered += partialCover;
            }
        }
        
        maxCovered = Math.max(maxCovered, covered);
    }
    
    return maxCovered;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(n log n)
空间复杂度O(n)

说明：

  • 时间复杂度：排序需要 O(n log n)，滑动窗口遍历需要 O(n)，总体为 O(n log n)
  • 空间复杂度：前缀和数组需要 O(n) 的额外空间

相关题目