文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

Alice 和 Bob 打算給花園里的 n 株植物澆水。
植物排成一行，從左到右進(jìn)行標(biāo)記，編號(hào)從 0 到 n - 1 。其中，第 i 株植物的位置是 x = i 。

每一株植物都需要澆特定量的水。
Alice 和 Bob 每人有一個(gè)水罐，最初是滿的 。他們按下面描述的方式完成澆水：

• Alice 按 從左到右 的順序給植物澆水，從植物 0 開(kāi)始。
• Bob 按 從右到左 的順序給植物澆水，從植物 n - 1 開(kāi)始。他們 同時(shí) 給植物澆水。
• 如果沒(méi)有足夠的水 完全 澆灌下一株植物，他 / 她會(huì)立即重新灌滿澆水罐。
• 不管植物需要多少水，澆水所耗費(fèi)的時(shí)間都是一樣的。
• 不能 提前重新灌滿水罐。
• 每株植物都可以由 Alice 或者 Bob 來(lái)澆水。
• 如果 Alice 和 Bob 到達(dá)同一株植物，那么當(dāng)前水罐中水更多的人會(huì)給這株植物澆水。如果他倆水量相同，那么 Alice 會(huì)給這株植物澆水。

給你一個(gè)下標(biāo)從 0 開(kāi)始的整數(shù)數(shù)組 plants ，數(shù)組由 n 個(gè)整數(shù)組成。其中，plants[i] 為第 i 株植物需要的水量。
另有兩個(gè)整數(shù) capacityA 和 capacityB 分別表示 Alice 和 Bob 水罐的容量。返回兩人澆灌所有植物過(guò)程中重新灌滿水罐的 次數(shù) 。

示例 1： 輸入：plants = [2,2,3,3], capacityA = 5, capacityB = 5 輸出：1 解釋： - 最初，Alice 和 Bob 的水罐中各有 5 單元水。 - Alice 給植物 0 澆水，Bob 給植物 3 澆水。 - Alice 和 Bob 現(xiàn)在分別剩下 3 單元和 2 單元水。 - Alice 有足夠的水給植物 1 ，所以她直接澆水。Bob 的水不夠給植物 2 ，所以他先重新裝滿水，再澆水。 所以，兩人澆灌所有植物過(guò)程中重新灌滿水罐的次數(shù) = 0 + 0 + 1 + 0 = 1 。示例 2： 輸入：plants = [2,2,3,3], capacityA = 3, capacityB = 4 輸出：2 解釋： - 最初，Alice 的水罐中有 3 單元水，Bob 的水罐中有 4 單元水。 - Alice 給植物 0 澆水，Bob 給植物 3 澆水。 - Alice 和 Bob 現(xiàn)在都只有 1 單元水，并分別需要給植物 1 和植物 2 澆水。 - 由于他們的水量均不足以澆水，所以他們重新灌滿水罐再進(jìn)行澆水。 所以，兩人澆灌所有植物過(guò)程中重新灌滿水罐的次數(shù) = 0 + 1 + 1 + 0 = 2 。示例 3： 輸入：plants = [5], capacityA = 10, capacityB = 8 輸出：0 解釋： - 只有一株植物 - Alice 的水罐有 10 單元水，Bob 的水罐有 8 單元水。因此 Alice 的水罐中水更多，她會(huì)給這株植物澆水。 所以，兩人澆灌所有植物過(guò)程中重新灌滿水罐的次數(shù) = 0 。示例 4： 輸入：plants = [1,2,4,4,5], capacityA = 6, capacityB = 5 輸出：2 解釋： - 最初，Alice 的水罐中有 6 單元水，Bob 的水罐中有 5 單元水。 - Alice 給植物 0 澆水，Bob 給植物 4 澆水。 - Alice 和 Bob 現(xiàn)在分別剩下 5 單元和 0 單元水。 - Alice 有足夠的水給植物 1 ，所以她直接澆水。Bob 的水不夠給植物 3 ，所以他先重新裝滿水，再澆水。 - Alice 和 Bob 現(xiàn)在分別剩下 3 單元和 1 單元水。 - 由于 Alice 的水更多，所以由她給植物 2 澆水。然而，她水罐里的水不夠給植物 2 ，所以她先重新裝滿水，再澆水。 所以，兩人澆灌所有植物過(guò)程中重新灌滿水罐的次數(shù) = 0 + 0 + 1 + 1 + 0 = 2 。示例 5： 輸入：plants = [2,2,5,2,2], capacityA = 5, capacityB = 5 輸出：1 解釋： Alice 和 Bob 都會(huì)到達(dá)中間的植物，并且此時(shí)他倆剩下的水量相同，所以 Alice 會(huì)給這株植物澆水。 由于她到達(dá)時(shí)只剩下 1 單元水，所以需要重新灌滿水罐。 這是唯一一次需要重新灌滿水罐的情況。 所以，兩人澆灌所有植物過(guò)程中重新灌滿水罐的次數(shù) = 1 。提示： n == plants.length 1 <= n <= 10^5 1 <= plants[i] <= 10^6 max(plants[i]) <= capacityA, capacityB <= 10^9

來(lái)源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/watering-plants-ii
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

• 雙指針?lè)謩e置于 0，n-1 向中間同步遍歷

class Solution { public:int minimumRefill(vector<int>& plants, int capacityA, int capacityB) {int ans = 0, i = 0, j = plants.size()-1;int wa = capacityA, wb = capacityB;while(i <= j){if(i < j){if(wa < plants[i]){wa = capacityA;ans++;}if(wb < plants[j]){wb = capacityB;ans++;}}else if(max(wa, wb) < plants[i]) ans++;wa -= plants[i];wb -= plants[j];i++,j--;}return ans;} };

132 ms 76.3 MB C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長(zhǎng)按或掃碼關(guān)注我的公眾號(hào)（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 2105. 给植物浇水 II（双指针）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。