题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是把一系列的数组当作一块块连续的白色瓷砖组，瓷砖组互不重叠，再给一个数字作为地毯长度，问地毯盖下去能覆盖的最长的瓷砖数是多少。

思路分享

  • 又是评鉴大佬（灵茶山艾府）题解的一集。

    https://leetcode.cn/problems/maximum-white-tiles-covered-by-a-carpet/solutions/1496434/by-endlesscheng-kdy9/

  • 首先我们可以思考一下如何覆盖地毯能尽可能覆盖最多瓷砖。易得（想几种情况比较，地毯右端在瓷砖组右侧，右端在中间，右端在左边），地毯的右侧如果直接与瓷砖组右侧对齐能尽可能地多覆盖瓷砖（拿地毯左侧与瓷砖组左侧对齐也可行）。

  • 那么可以想象地毯（窗口）如何滑动能够比较高效地计算出最长的情况。由上面的推导式，想要让窗口单向滑动，先要对瓷砖组做排序，按第一位，也就是瓷砖组的起点做升序排序。

  • 那么计算窗口内瓷砖数量呢？其实只要每次窗口滑动，就把新瓷砖组的瓷砖数加入，就能直到窗口内的总瓷砖数。要知道窗口最左侧的瓷砖组是否需要排除，只要在这个最左侧的瓷砖组的右侧加上地毯长度，发现这个值还是比目前最右侧的值小，说明地毯无法保持与右侧对齐，这是就要去除最左侧的瓷砖组。

  • 说完了加入和排除策略，那么如果地毯左侧处于某个瓷砖组中间呢？只要拿最左侧瓷砖组的左侧加上地毯长度与当前最右侧瓷砖组右侧之差与零取一个最大值，就能找出当前地毯没有覆盖最左侧瓷砖的长度，如果长度为负数也能取到零。

代码解答（强烈建议自行解答后再看）

  • 参考题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int maximumWhiteTiles(vector<vector<int>>& tiles, int carpetLen) {
        ranges::sort(tiles, {}, [](auto &t){return t[0];});
        int left = 0;
        int cover = 0;
        int ans = 0;
        for (const auto &ti : tiles) {
            cover += ti[1]-ti[0]+1;
            while(tiles[left][1]+carpetLen-1 < ti[1]) {
                cover -= tiles[left][1]-tiles[left][0]+1;
                left++;
            }
            int uncover = max(0, ti[1]-carpetLen+1-tiles[left][0]);
            ans = max(ans, cover-uncover);
        }
        return ans;
    }
};