给植物浇水

难度: Medium

你打算用一个水罐给花园里的 n 株植物浇水。植物排成一行，从左到右进行标记，编号从 0 到 n - 1 。其中，第 i 株植物的位置是 x = i 。x = -1 处有一条河，你可以在那里重新灌满你的水罐。

每一株植物都需要浇特定量的水。你将会按下面描述的方式完成浇水：

按从左到右的顺序给植物浇水。
在给当前植物浇完水之后，如果你没有足够的水完全浇灌下一株植物，那么你就需要返回河边重新装满水罐。
你不能提前重新灌满水罐。

最初，你在河边（也就是，x = -1），在 x 轴上每移动 一个单位 都需要一步。

给你一个下标从 0 开始的整数数组 plants ，数组由 n 个整数组成。其中，plants[i] 为第 i 株植物需要的水量。另有一个整数 capacity 表示水罐的容量，返回浇灌所有植物需要的步数。

示例 1：

输入：plants = [2,2,3,3], capacity = 5
输出：14
解释：从河边开始，此时水罐是装满的：
- 走到植物 0 (1 步) ，浇水。水罐中还有 3 单位的水。
- 走到植物 1 (1 步) ，浇水。水罐中还有 1 单位的水。
- 由于不能完全浇灌植物 2 ，回到河边取水 (2 步)。
- 走到植物 2 (3 步) ，浇水。水罐中还有 2 单位的水。
- 由于不能完全浇灌植物 3 ，回到河边取水 (3 步)。
- 走到植物 3 (4 步) ，浇水。
需要的步数是 = 1 + 1 + 2 + 3 + 3 + 4 = 14 。

示例 2：

输入：plants = [1,1,1,4,2,3], capacity = 4
输出：30
解释：从河边开始，此时水罐是装满的：
- 走到植物 0，1，2 (3 步) ，浇水。回到河边取水 (3 步)。
- 走到植物 3 (4 步) ，浇水。回到河边取水 (4 步)。
- 走到植物 4 (5 步) ，浇水。回到河边取水 (5 步)。
- 走到植物 5 (6 步) ，浇水。
需要的步数是 = 3 + 3 + 4 + 4 + 5 + 5 + 6 = 30 。

示例 3：

输入：plants = [7,7,7,7,7,7,7], capacity = 8
输出：49
解释：每次浇水都需要重新灌满水罐。
需要的步数是 = 1 + 1 + 2 + 2 + 3 + 3 + 4 + 4 + 5 + 5 + 6 + 6 + 7 = 49 。

提示：

n == plants.length
1 <= n <= 1000
1 <= plants[i] <= 10⁶
max(plants[i]) <= capacity <= 10⁹

Submission

运行时间: 24 ms

内存: 16.1 MB

class Solution:
    def wateringPlants(self, plants: List[int], capacity: int) -> int:
        length = len(plants)
        ans = 0
        cur = capacity
        for i in range(length):
            if cur >= plants[i]:
                ans += 1
                cur = cur - plants[i]
                continue
            else:
                ans = ans + i + i + 1
                cur = capacity - plants[i]
                continue
        return ans

Explain

题解的核心思路是模拟整个浇水过程。从河边开始，遍历每株植物，检查当前水罐的剩余水量是否足以浇灌当前植物。如果足够，则向前走一步，更新剩余水量。如果不足，则先回到河边重新装满水罐，再前往当前植物。回河边的步数等于当前位置的两倍（来回），然后再加一步表示浇水的动作。此过程持续直到所有植物被浇水。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def wateringPlants(self, plants: List[int], capacity: int) -> int:
        length = len(plants)  # 获取植物的数量
        ans = 0  # 初始化步数为0
        cur = capacity  # 当前水罐的水量设置为满
        for i in range(length):  # 遍历每株植物
            if cur >= plants[i]:  # 如果当前水量足够浇水
                ans += 1  # 前进一步并浇水
                cur -= plants[i]  # 减少水罐中的水量
            else:  # 如果水不够
                ans += i + i + 1  # 回到河边取水，并走到当前植物位置
                cur = capacity - plants[i]  # 重新装满水罐，减去当前植物需要的水量
        return ans  # 返回总步数

Explore

是的，如果初始水罐未满，这将影响计算结果。算法设计是基于水罐从满的状态开始的假设。如果初始时水罐未满，可能会导致在预期之前就需要回到河边重新装水，这样会增加额外的步数。因此，在实际应用中应确保算法开始前水罐是满的，或者修改算法以适应不同的初始水量状况。

在计算回河边取水的步数时，使用`i + i + 1`表示从当前位置回到起点（河边）再回到当前位置的总步数。这里的`i`是当前植物的索引，因此`i + i`表示往返的步数。额外的`+1`是代表浇水的动作。即每次到达一株植物的位置后，需要进行一次浇水操作，这个操作也计入总步数。

根据题解中的算法逻辑，如果最后一株植物浇水后水量正好用完，算法不会错误地返回河边。因为算法检查水量是否足够浇下一株植物前，已经完成了对当前植物的浇水操作。只有当发现下一株植物的水量不足时，才会考虑返回河边。因此，如果是最后一株植物且水量正好用完，则不会有额外的返回河边的动作，算法将正常结束。