Medium

题目描述

你想要在花园中给 n 棵植物浇水，你有一个浇水壶。植物排成一行，标记为从 0 到 n - 1，从左到右第 i 棵植物位于 x = i 位置。在 x = -1 处有一条河，你可以在那里重新装满浇水壶。

每棵植物需要特定数量的水。你将按以下方式给植物浇水：

  • 按从左到右的顺序给植物浇水。
  • 给当前植物浇水后，如果你没有足够的水来完全浇灌下一棵植物，则返回河边重新装满浇水壶。
  • 你不能提前重新装满浇水壶。

你最初在河边（即 x = -1）。在 x 轴上移动一个单位需要一步。

给定一个长度为 n 的 0 索引整数数组 plants，其中 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

示例 3：

输入：plants = [7,7,7,7,7,7,7], capacity = 8
输出：49

约束条件：

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

解题思路

解题思路

这是一个模拟题，我们需要按照题目描述的规则来模拟整个浇水过程。

基本思路

  1. 初始状态：我们从河边（位置 -1）开始，浇水壶已装满（容量为 capacity）
  2. 移动规则：每次移动一个位置需要 1 步
  3. 浇水规则：
    • 按从左到右的顺序浇水
    • 给当前植物浇水后，检查剩余水量是否足够浇下一棵植物
    • 如果不够，必须回到河边重新装满

算法步骤

  1. 初始化当前水量为满容量，当前位置为 -1，总步数为 0
  2. 遍历每棵植物：
    • 计算从当前位置走到植物 i 的步数
    • 给植物 i 浇水，更新剩余水量
    • 如果这不是最后一棵植物，检查剩余水量是否足够浇下一棵植物
    • 如果不够，计算回到河边的步数，重新装满水壶
  3. 返回总步数

这种方法的时间复杂度是 O(n)，空间复杂度是 O(1)，是最优解法。

代码实现

class Solution {
public:
    int wateringPlants(vector<int>& plants, int capacity) {
        int steps = 0;
        int currentWater = capacity;
        int currentPos = -1;
        
        for (int i = 0; i < plants.size(); i++) {
            // 走到当前植物的步数
            steps += i - currentPos;
            currentPos = i;
            
            // 给当前植物浇水
            currentWater -= plants[i];
            
            // 如果不是最后一棵植物，检查是否需要回河边装水
            if (i < plants.size() - 1 && currentWater < plants[i + 1]) {
                // 回到河边的步数
                steps += i + 1;
                currentPos = -1;
                currentWater = capacity;
            }
        }
        
        return steps;
    }
};

class Solution:
    def wateringPlants(self, plants: List[int], capacity: int) -> int:
        steps = 0
        current_water = capacity
        current_pos = -1
        
        for i in range(len(plants)):
            # 走到当前植物的步数
            steps += i - current_pos
            current_pos = i
            
            # 给当前植物浇水
            current_water -= plants[i]
            
            # 如果不是最后一棵植物，检查是否需要回河边装水
            if i < len(plants) - 1 and current_water < plants[i + 1]:
                # 回到河边的步数
                steps += i + 1
                current_pos = -1
                current_water = capacity
        
        return steps

public class Solution {
    public int WateringPlants(int[] plants, int capacity) {
        int steps = 0;
        int currentWater = capacity;
        int currentPos = -1;
        
        for (int i = 0; i < plants.Length; i++) {
            // 走到当前植物的步数
            steps += i - currentPos;
            currentPos = i;
            
            // 给当前植物浇水
            currentWater -= plants[i];
            
            // 如果不是最后一棵植物，检查是否需要回河边装水
            if (i < plants.Length - 1 && currentWater < plants[i + 1]) {
                // 回到河边的步数
                steps += i + 1;
                currentPos = -1;
                currentWater = capacity;
            }
        }
        
        return steps;
    }
}

var wateringPlants = function(plants, capacity) {
    let steps = 0;
    let currentWater = capacity;
    let currentPos = -1;
    
    for (let i = 0; i < plants.length; i++) {
        // 走到当前植物的步数
        steps += i - currentPos;
        currentPos = i;
        
        // 给当前植物浇水
        currentWater -= plants[i];
        
        // 如果不是最后一棵植物，检查是否需要回河边装水
        if (i < plants.length - 1 && currentWater < plants[i + 1]) {
            // 回到河边的步数
            steps += i + 1;
            currentPos = -1;
            currentWater = capacity;
        }
    }
    
    return steps;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历所有植物一次，每个植物的处理时间为常数
空间复杂度O(1)只使用了常数个额外变量来记录状态

相关题目