X

LEETCODE 1326. Minimum Number of Taps to Open to Water a Garden 解题思路分析

题目大意:

灌溉花园的最少水龙头数目

在 x 轴上有一个一维的花园。花园长度为 n,从点 0 开始,到点 n 结束。

花园里总共有 n + 1 个水龙头,分别位于 [0, 1, …, n] 。

给你一个整数 n 和一个长度为 n + 1 的整数数组 ranges ,其中 ranges[i] (下标从 0 开始)表示:如果打开点 i 处的水龙头,可以灌溉的区域为 [i –  ranges[i], i + ranges[i]] 。

请你返回可以灌溉整个花园的 最少水龙头数目 。如果花园始终存在无法灌溉到的地方,请你返回 -1 。

示例 1:

输入:n = 5, ranges = [3,4,1,1,0,0]
输出:1
解释:
 点 0 处的水龙头可以灌溉区间 [-3,3]
 点 1 处的水龙头可以灌溉区间 [-3,5]
 点 2 处的水龙头可以灌溉区间 [1,3]
 点 3 处的水龙头可以灌溉区间 [2,4]
 点 4 处的水龙头可以灌溉区间 [4,4]
 点 5 处的水龙头可以灌溉区间 [5,5]
 只需要打开点 1 处的水龙头即可灌溉整个花园 [0,5] 。

示例 2:

输入:n = 3, ranges = [0,0,0,0]
输出:-1
解释:即使打开所有水龙头,你也无法灌溉整个花园。

示例 3:

输入:n = 7, ranges = [1,2,1,0,2,1,0,1]
输出:3

示例 4:

输入:n = 8, ranges = [4,0,0,0,0,0,0,0,4]
输出:2

示例 5:

输入:n = 8, ranges = [4,0,0,0,4,0,0,0,4]
输出:1

提示:

  • 1 <= n <= 10^4
  • ranges.length == n + 1
  • 0 <= ranges[i] <= 100

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1326

解题思路分析:

本题一开始想到的是使用递归思路,首层递归,循环整个花园从左至右所有的喷头,当前喷头的覆盖范围需要一个cost,当前喷头范围左边界到当前递归总范围的左边,以及当前喷头范围的右边界到当前递归总范围的右边,递归到子问题求解。两个子问题的解加一即是当前解,循环所有喷头后计算一个最小解即是当前递归的最优解。

然而提交后发现这种解法效率很低,处于TLE的边缘。于是想到了下面这种贪心算法。

首先我们算出每个喷头的范围left和right,如果left小于0,记为0,如果right大于n,记为n。我们将每个范围看作是一个线段或者区间,将区间存入一个数组maxRange[],数组下标为该区间的left,该下标的值为区间的right。循环时,如果遇到相同left下标的值已经存在于maxRange[left]时,更新最大值存入,即代表始于当前left的区间,最远能够达到right位置。

这时问题就变的简单了,我们只需要在一堆线段中,找出最少能覆盖整个区域的线段数即可。从left为0开始找,此时maxRange[0]代表0开始的线段最远能到达的index。接下来,我们需要在[left+1, maxRange[left]]范围内一条能够到达的最远的线段即可,如果该最远线段小于等于当前maxRange[left],说明与当前相交的所有线段中没有能够超越maxRange[left]点的线段了,因此返回-1。反之继续向后寻找,直到找到某条线段能到达终点为止。

实现代码:

public int minTaps(int n, int[] ranges) {
    // 所有喷头覆盖的区间
    int[] maxRanges = new int[n+1];
    // 循环每一个喷头
    for(int i=0;i<ranges.length;i++){
        // 喷头覆盖区间的左下标
        int left=i-ranges[i];
        // 左下标小于0时,设为0
        if(left<0) left=0;
        // 喷头覆盖区间的右下标
        int right=i+ranges[i];
        // 右下标大于n时,设为n
        if(right>n) right=n;
        // 将区间存入maxRanges
        // maxRanges[left]代表左下标为left的区间最远可以到达的坐标
        maxRanges[left] =Math.max(maxRanges[left], right);
    }
    // 找出能够覆盖整个区间的最少区间个数
    // 第一个区间从0开始,maxRanges[0]结束
    int l=0,r=maxRanges[0];
    int res=1; // 返回结果
    // 当右区间小于n时循环
    while(r<n){
        // 找到下一个区间,下一个区间的left在当前区间内
        // 并且下一个区间的right大于当前区间right
        // 找到符合上述要求的一个right最大区间
        int maxRight=r;
        int maxLeft=l;
        for(int i=l;i<=r;i++){
            if(maxRanges[i]>maxRight){
                maxRight=maxRanges[i];
                maxLeft=i;
            }
        }
        // 如果最大right不能大于当前right,返回-1
        if(maxRight==r) return -1;
        // 更新下一个区间的left和right
        r=maxRight;
        l=maxLeft+1;
        res++;
    }
    return res;
}

本题解法执行时间为2ms。

Runtime: 3 ms, faster than 100.00% of Java online submissions for Minimum Number of Taps to Open to Water a Garden.

Memory Usage: 47.2 MB, less than 100.00% of Java online submissions for Minimum Number of Taps to Open to Water a Garden.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1326-minimum-number-of-taps-to-open-to-water-a-garden-解题思路分析/
Categories: leetcode
kwantong: