KK's blog

每天积累多一些

0%

LeetCode 2079 Watering Plants

Posted on Disqus:

LeetCode 2079 Watering Plants

You want to water n plants in your garden with a watering can. The plants are arranged in a row and are labeled from 0 to n - 1 from left to right where the i<sup>th</sup> plant is located at x = i. There is a river at x = -1 that you can refill your watering can at.

Each plant needs a specific amount of water. You will water the plants in the following way:

  • Water the plants in order from left to right.
  • After watering the current plant, if you do not have enough water to completely water the next plant, return to the river to fully refill the watering can.
  • You cannot refill the watering can early.

You are initially at the river (i.e., x = -1). It takes one step to move one unit on the x-axis.

Given a 0-indexed integer array plants of n integers, where plants[i] is the amount of water the i<sup>th</sup> plant needs, and an integer capacity representing the watering can capacity, return the number of steps needed to water all the plants.

Example 1:

**Input:** plants = [2,2,3,3], capacity = 5
**Output:** 14
**Explanation:** Start at the river with a full watering can:
- Walk to plant 0 (1 step) and water it. Watering can has 3 units of water.
- Walk to plant 1 (1 step) and water it. Watering can has 1 unit of water.
- Since you cannot completely water plant 2, walk back to the river to refill (2 steps).
- Walk to plant 2 (3 steps) and water it. Watering can has 2 units of water.
- Since you cannot completely water plant 3, walk back to the river to refill (3 steps).
- Walk to plant 3 (4 steps) and water it.
Steps needed = 1 + 1 + 2 + 3 + 3 + 4 = 14.

Example 2:

**Input:** plants = [1,1,1,4,2,3], capacity = 4
**Output:** 30
**Explanation:** Start at the river with a full watering can:
- Water plants 0, 1, and 2 (3 steps). Return to river (3 steps).
- Water plant 3 (4 steps). Return to river (4 steps).
- Water plant 4 (5 steps). Return to river (5 steps).
- Water plant 5 (6 steps).
Steps needed = 3 + 3 + 4 + 4 + 5 + 5 + 6 = 30.

Example 3:

**Input:** plants = [7,7,7,7,7,7,7], capacity = 8
**Output:** 49
**Explanation:** You have to refill before watering each plant.
Steps needed = 1 + 1 + 2 + 2 + 3 + 3 + 4 + 4 + 5 + 5 + 6 + 6 + 7 = 49.

Constraints:

  • n == plants.length
  • 1 <= n <= 1000
  • 1 <= plants[i] <= 10<sup>6</sup>
  • max(plants[i]) <= capacity <= 10<sup>9</sup>

题目大意：

x坐标上分别是浇每棵植物需要的水量，用数组plants表示，-1上为河水可以打水，capacity是容器大小。若发现水不够，就要回到河里将容器打满水。问浇完所有植物的总步数

解题思路：

此题类似于Leetcode 2073，可以按部就班按每个plant计算，但是为了提高效率，一般采取归结为更高一层次计算。
这题更高层次是每次去洒水再回去河边作为一个循环。最后一个循环不用回河边所以是单程。

解题步骤：

  1. 计算一次来回的距离，条件为剩余的水不够浇该次的植物
  2. 退出循环后，计算单程距离

注意事项：

  1. 如果满足capacity也要递归到下一轮再计算，也就是Line 5取等号

Python代码：

1
2
3
4
5
6
7
8
9
10
11
def wateringPlants(self, plants: List[int], capacity: int) -> int:
	sum, steps = 0, 0
	for i, n in enumerate(plants):
		sum += plants[i]
		if sum <= capacity:
			continue
		steps += i * 2  # back to river
		sum = plants[i]
	if sum > 0:
		steps += len(plants)
	return steps

算法分析：

时间复杂度为O(n)，空间复杂度O(1)。

Free mock interview