Medium

题目描述

Alice 和 Bob 想要给花园里的 n 株植物浇水。植物排成一行，从左到右用 0 到 n - 1 标记，其中第 i 株植物位于 x = i 处。

每株植物都需要特定数量的水。Alice 和 Bob 都有一个水壶，最初是满的。他们按以下方式给植物浇水：

  • Alice 按从左到右的顺序给植物浇水，从第 0 株植物开始。Bob 按从右到左的顺序给植物浇水，从第 (n - 1) 株植物开始。他们同时开始给植物浇水。
  • 给每株植物浇水需要的时间相同，不管它需要多少水。
  • Alice/Bob 必须给植物浇水，如果他们的水壶里有足够的水来完全浇灌它。否则，他们首先重新装满水壶（瞬间），然后给植物浇水。
  • 如果 Alice 和 Bob 都到达同一株植物，那么当前水壶里水更多的人应该给这株植物浇水。如果他们水壶里的水一样多，那么 Alice 应该给这株植物浇水。

给定一个长度为 n 的整数数组 plants，其中 plants[i] 是第 i 株植物需要的水量，以及两个整数 capacityA 和 capacityB，分别代表 Alice 和 Bob 水壶的容量，返回他们浇完所有植物需要重新装满水壶的次数。

示例 1：

输入：plants = [2,2,3,3], capacityA = 5, capacityB = 5
输出：1

示例 2：

输入：plants = [2,2,3,3], capacityA = 3, capacityB = 4
输出：2

示例 3：

输入：plants = [5], capacityA = 10, capacityB = 8
输出：0

提示：

  • n == plants.length
  • 1 <= n <= 10^5
  • 1 <= plants[i] <= 10^6
  • max(plants[i]) <= capacityA, capacityB <= 10^9

解题思路

解题思路

这是一道模拟题，核心思想是通过双指针模拟 Alice 和 Bob 同时浇水的过程。

关键分析点：

  1. 双指针移动：Alice 从左边开始（left = 0），Bob 从右边开始（right = n-1），每次各自移动一步
  2. 相遇条件：当 left >= right 时，两人相遇或交错
  3. 浇水规则：
    • 如果水壶容量不足，先重新装满再浇水
    • 相遇时，水更多的人浇水；相等时 Alice 浇水

解法步骤：

  1. 初始化两个指针 left = 0, right = n-1，以及当前水量 waterA = capacityA, waterB = capacityB
  2. 当 left < right 时（还未相遇）：
    • Alice 检查能否浇水 plants[left]，不够就重新装满
    • Bob 检查能否浇水 plants[right]，不够就重新装满
    • 两人分别向中间移动一步
  3. 当 left == right 时（相遇在同一植物）：
    • 比较两人当前水量，水多的人浇水（相等时 Alice 浇水）
    • 如果选中的人水量不足，需要重新装满

这种方法的优势是直接模拟了题目描述的过程，逻辑清晰，时间复杂度为 O(n)。

代码实现

class Solution {
public:
    int minimumRefill(vector<int>& plants, int capacityA, int capacityB) {
        int n = plants.size();
        int left = 0, right = n - 1;
        int waterA = capacityA, waterB = capacityB;
        int refills = 0;
        
        while (left < right) {
            // Alice浇水
            if (waterA < plants[left]) {
                refills++;
                waterA = capacityA;
            }
            waterA -= plants[left];
            left++;
            
            // Bob浇水
            if (waterB < plants[right]) {
                refills++;
                waterB = capacityB;
            }
            waterB -= plants[right];
            right--;
        }
        
        // 处理相遇情况
        if (left == right) {
            int maxWater = max(waterA, waterB);
            if (maxWater < plants[left]) {
                refills++;
            }
        }
        
        return refills;
    }
};

class Solution:
    def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:
        n = len(plants)
        left, right = 0, n - 1
        waterA, waterB = capacityA, capacityB
        refills = 0
        
        while left < right:
            # Alice浇水
            if waterA < plants[left]:
                refills += 1
                waterA = capacityA
            waterA -= plants[left]
            left += 1
            
            # Bob浇水
            if waterB < plants[right]:
                refills += 1
                waterB = capacityB
            waterB -= plants[right]
            right -= 1
        
        # 处理相遇情况
        if left == right:
            max_water = max(waterA, waterB)
            if max_water < plants[left]:
                refills += 1
        
        return refills

public class Solution {
    public int MinimumRefill(int[] plants, int capacityA, int capacityB) {
        int n = plants.Length;
        int left = 0, right = n - 1;
        int waterA = capacityA, waterB = capacityB;
        int refills = 0;
        
        while (left < right) {
            // Alice浇水
            if (waterA < plants[left]) {
                refills++;
                waterA = capacityA;
            }
            waterA -= plants[left];
            left++;
            
            // Bob浇水
            if (waterB < plants[right]) {
                refills++;
                waterB = capacityB;
            }
            waterB -= plants[right];
            right--;
        }
        
        // 处理相遇情况
        if (left == right) {
            int maxWater = Math.Max(waterA, waterB);
            if (maxWater < plants[left]) {
                refills++;
            }
        }
        
        return refills;
    }
}

var minimumRefill = function(plants, capacityA, capacityB) {
    let n = plants.length;
    let alice = 0, bob = n - 1;
    let waterA = capacityA, waterB = capacityB;
    let refills = 0;
    
    while (alice < bob) {
        // Alice waters from left
        if (waterA < plants[alice]) {
            refills++;
            waterA = capacityA;
        }
        waterA -= plants[alice];
        alice++;
        
        // Bob waters from right
        if (waterB < plants[bob]) {
            refills++;
            waterB = capacityB;
        }
        waterB -= plants[bob];
        bob--;
    }
    
    // Handle middle plant if exists
    if (alice === bob) {
        if (waterA >= waterB) {
            if (waterA < plants[alice]) {
                refills++;
            }
        } else {
            if (waterB < plants[alice]) {
                refills++;
            }
        }
    }
    
    return refills;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)需要遍历所有植物一次，每株植物最多被访问一次
空间复杂度O(1)只使用了常数个变量存储指针位置和水量信息

相关题目