LeetCode-2079. 給植物澆水【數組 模擬】
- 題目描述：
- 解題思路一：簡單的模擬題，初始化為0，考慮先不澆灌每一個植物
- 解題思路二：初始化為n，考慮每一個植物需要澆灌
- 解題思路三：0
題目描述：
你打算用一個水罐給花園里的 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] <= 106
max(plants[i]) <= capacity <= 109
解題思路一：簡單的模擬題，初始化為0，考慮先不澆灌每一個植物
class Solution:def wateringPlants(self, plants: List[int], capacity: int) -> int:cur = capacityans = 0for i in range(len(plants)):if cur >= plants[i]:cur -= plants[i]ans += 1else:cur = capacity - plants[i]ans += 2 * i + 1# print(i, ans)return ans
時間復雜度：O(n)
空間復雜度：O(1)
解題思路二：初始化為n，考慮每一個植物需要澆灌
class Solution:def wateringPlants(self, plants: List[int], capacity: int) -> int:ans = len(plants)water = capacityfor i, need in enumerate(plants):if water < need:ans += i * 2water = capacitywater -= needreturn ans
時間復雜度：O(n)
空間復雜度：O(1)
解題思路三：0
時間復雜度：O(n)
空間復雜度：O(n)
? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ?
)
