2271. 毯子覆盖的最多白色砖块数

Difficulty
Medium
Tags
滑动窗口
URL
https://leetcode.cn/problems/maximum-white-tiles-covered-by-a-carpet/
Star
给你一个二维整数数组 tiles ，其中 tiles[i] = [li, ri] ，表示所有在 li <= j <= ri 之间的每个瓷砖位置 j 都被涂成了白色。
同时给你一个整数 carpetLen ，表示可以放在 任何位置 的一块毯子。
请你返回使用这块毯子，最多 可以盖住多少块瓷砖。
示例 1：
notion imagenotion image
输入：tiles = [[1,5],[10,11],[12,18],[20,25],[30,32]], carpetLen = 10
输出：9
解释：将毯子从瓷砖 10 开始放置。
总共覆盖 9 块瓷砖，所以返回 9 。
注意可能有其他方案也可以覆盖 9 块瓷砖。
可以看出，瓷砖无法覆盖超过 9 块瓷砖。
示例 2：
notion imagenotion image
输入：tiles = [[10,11],[1,1]], carpetLen = 2
输出：2
解释：将毯子从瓷砖 10 开始放置。
总共覆盖 2 块瓷砖，所以我们返回 2 。
提示：
  • 1 <= tiles.length <= 5 * 104
  • tiles[i].length == 2
  • 1 <= li <= ri <= 109
  • 1 <= carpetLen <= 109
  • tiles 互相 不会重叠 。
通过次数2,384提交次数9,124

法 1 滑动窗口

思路
拿毯子在地板上向右滑动，记下最大的覆盖范围。
需要注意的细节有：
  • 地板区间需要排序
  • 可能存在 地板范围没地毯长的情况，此时答案就是全部地板的覆盖范围
  • 当当前范围 大于等于 地毯时，需要计算 真实的覆盖范围，此时可能出现两种情况：
    • 一种是地毯右边界 触碰到了 r 块地板区域；此时真实的覆盖范围 为 now - 第r 块地板范围 + 在第 r 块地板 触碰的范围
    • 一种是没触碰到，此时真实的覆盖范围 为 now - 第r 块地板范围
题解
class Solution:
    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:
        tiles.sort()
        res = 0
        l, r = 0, 0
        wds = 0
        # 遍历每个起点对应的 终点
        while l < len(tiles):
            # 不够，向右扩张
            while r < len(tiles) and tiles[l][0] + carpetLen - 1 >= tiles[r][0]:
                wds += tiles[r][1] - tiles[r][0] + 1
                r += 1
            # 计算真实的覆盖
            real_cover = wds
            if tiles[l][0] + carpetLen - 1 < tiles[r-1][1]:
                real_cover -= tiles[r-1][1] - (tiles[l][0] + carpetLen - 1)

            res = max(res, real_cover)
            # 起点向后移动
            wds -= tiles[l][1] - tiles[l][0] + 1
            l += 1

        return res
class Solution:
    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:
        # now 记录的是 l , r 能覆盖的区间
        now = 0
        l, r = 0, 0 
        tiles.sort()
        ans = 0
        while r < len(tiles):
            now += tiles[r][1] - tiles[r][0] + 1

            while l <= r and tiles[r][1] - tiles[l][0] + 1 >= carpetLen:
                # 减去一些边界
                cur_range = now - \
                            (tiles[r][1] - tiles[r][0] + 1) + \
                            max(0, tiles[l][0] + carpetLen - 1 - tiles[r][0] + 1)
                ans = max(ans, cur_range)
            
                # 开始收缩
                now -= tiles[l][1] - tiles[l][0] + 1
                l += 1
                
            r += 1
        # 可能存在 不够的情况，此时 ans 就是全部的覆盖范围
        return ans if ans > 0 else now
展示一种错误的写法！以下写法是错误的，它并不是以每一块毯子为起点遍历的，而是以每一块毯子为终点遍历的，因此wa
class Solution:
    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:
        wds = 0
        l, r = 0, 0
        tiles.sort()
        res = 0
        while r < len(tiles):
            wds += tiles[r][1] - tiles[r][0] + 1
            
            # 覆盖不到 第 r 块
            while tiles[l][0] + carpetLen - 1 < tiles[r][0]:
                wds -= tiles[l][1] - tiles[l][0] + 1
                l += 1

            cover = wds
            if tiles[l][0] + carpetLen - 1 < tiles[r][1]:
                temp = tiles[r][1] - (tiles[l][0] + carpetLen - 1)
                cover -= temp

            res = max(res, cover)
            r += 1

        return res