毯子覆盖的最多白色砖块数
难度:
标签:
题目描述
You are given a 2D integer array tiles where tiles[i] = [li, ri] represents that every tile j in the range li <= j <= ri is colored white.
You are also given an integer carpetLen, the length of a single carpet that can be placed anywhere.
Return the maximum number of white tiles that can be covered by the carpet.
Example 1:
Input: tiles = [[1,5],[10,11],[12,18],[20,25],[30,32]], carpetLen = 10 Output: 9 Explanation: Place the carpet starting on tile 10. It covers 9 white tiles, so we return 9. Note that there may be other places where the carpet covers 9 white tiles. It can be shown that the carpet cannot cover more than 9 white tiles.
Example 2:
Input: tiles = [[10,11],[1,1]], carpetLen = 2 Output: 2 Explanation: Place the carpet starting on tile 10. It covers 2 white tiles, so we return 2.
Constraints:
1 <= tiles.length <= 5 * 104tiles[i].length == 21 <= li <= ri <= 1091 <= carpetLen <= 109- The
tilesare non-overlapping.
代码结果
运行时间: 139 ms, 内存: 35.7 MB
/*
* 思路：
* 1. 使用Java Stream对瓷砖进行排序。
* 2. 使用滑动窗口算法计算在任意位置放置毯子所能覆盖的最大瓷砖数。
*/
import java.util.Arrays;
import java.util.Comparator;
import java.util.stream.IntStream;
public class Solution {
public int maximumWhiteTiles(int[][] tiles, int carpetLen) {
tiles = Arrays.stream(tiles)
.sorted(Comparator.comparingInt(a -> a[0]))
.toArray(int[][]::new);
int maxCovered = 0;
int n = tiles.length;
int cover = 0;
int j = 0;
for (int i = 0; i < n; i++) {
while (j < n && tiles[j][1] - tiles[i][0] + 1 <= carpetLen) {
cover += tiles[j][1] - tiles[j][0] + 1;
j++;
}
if (j < n && tiles[i][0] + carpetLen - 1 >= tiles[j][0]) {
maxCovered = Math.max(maxCovered, cover + tiles[i][0] + carpetLen - tiles[j][0]);
} else {
maxCovered = Math.max(maxCovered, cover);
}
cover -= tiles[i][1] - tiles[i][0] + 1;
}
return maxCovered;
}
}解释
方法:
这个问题可以通过排序和滑动窗口技术来解决。首先，将瓷砖按照起始位置排序。定义两个指针l和r，表示当前正在考虑的瓷砖范围。变量cnt用于记录当前窗口内瓷砖的总数。从左到右遍历瓷砖，每次移动左指针l，减去左边瓷砖的数量，并尝试向右扩展右指针r，直到毯子的右边界超过了r指针指向的瓷砖的右端。每次右移r时，更新cnt以包括新增的瓷砖。如果毯子的右边界落在r指向的瓷砖内部，计算并更新可能的额外覆盖数量。最终，ans记录了所有可能情况下的最大覆盖数。
时间复杂度:
O(n log n)
空间复杂度:
O(1)
代码细节讲解
🦆
在算法实现中，为什么首先需要对瓷砖按起始位置进行排序？排序的目的是什么？
▷🦆
在滑动窗口技术中，指针r是如何向右扩展的？r指针在何时停止移动？
▷🦆
在计算额外覆盖瓷砖数量时，为什么使用`max(0, tiles[l][0] + carpetLen - tiles[r][0])`而不是考虑`tiles[r][1]`？
▷