?

每天 3 分鐘，走上算法的逆襲之路。

?

前文合集

每日一道 LeetCode 前文合集

代碼倉庫

GitHub：https://github.com/meteor1993/LeetCode

Gitee：https://gitee.com/inwsy/LeetCode

題目：盛最多水的容器

難度：「中等」

題目來源：https://leetcode-cn.com/problems/container-with-most-water/

給你 n 個(gè)非負(fù)整數(shù) a1，a2，...，an，每個(gè)數(shù)代表坐標(biāo)中的一個(gè)點(diǎn)?(i, ai) 。在坐標(biāo)內(nèi)畫 n 條垂直線，垂直線 i 的兩個(gè)端點(diǎn)分別為?(i, ai) 和 (i, 0)。找出其中的兩條線，使得它們與 x 軸共同構(gòu)成的容器可以容納最多的水。

說明：你不能傾斜容器，且 n 的值至少為 2。

圖中垂直線代表輸入數(shù)組 [1,8,6,2,5,4,8,3,7]。在此情況下，容器能夠容納水(表示為藍(lán)色部分)的最大值為 49。

示例：

輸入：[1,8,6,2,5,4,8,3,7]
輸出：49

解題思路

今天這道題蠻有意思的，給出一個(gè)數(shù)組，實(shí)際上是在求這個(gè)數(shù)組之間可以組成的最大面積。

這道題正統(tǒng)的解法是使用雙指針，因?yàn)槭窃跀?shù)組之間灌水，能容納的水有多少是取決于那個(gè)最小的數(shù)字，所以我們先把兩個(gè)指針分別指向數(shù)組的頭和尾，先求一下當(dāng)前的面積，然后比較下頭尾的大小，每次移動(dòng)較小的那個(gè)指針，把整個(gè)數(shù)組迭代一遍，取出其中的最大值即可。

public?int?maxArea(int[]?height)?{
????int?len?=?height.length;
????int?start?=?0,?end?=?len?-?1;
????int?maxArea?=?0;
????while?(start?!=?end)?{
????????int?area?=?Math.min(height[start],?height[end])?*?(end?-?start);
????????maxArea?=?Math.max(area,?maxArea);
????????if?(height[start]?????????????start++;
????????}?else?{
????????????end--;
????????}
????}
????return?maxArea;
}

代碼看起來不難，聲明一點(diǎn)哈，上面這個(gè)方案不是我想出來的，是看了答案的提示以后才知道的。

但是這里面有個(gè)問題，為什么這種方案是可以找到最大的面積的，難道就不會(huì)存在其他的情況么？

下面的這個(gè)證明方案同樣來自于答案當(dāng)中，用來證明上面這個(gè)方案的正確性。

雙指針代表的是可以作為容器邊界的所有位置的范圍。在一開始，雙指針指向數(shù)組的左右邊界，表示數(shù)組中所有的位置都可以作為容器的邊界，因?yàn)槲覀冞€沒有進(jìn)行過任何嘗試。

在這之后，我們每次將對應(yīng)的數(shù)字較小的那個(gè)指針往另一個(gè)指針 方向移動(dòng)一個(gè)位置，就表示我們認(rèn)為這個(gè)指針不可能再作為容器的邊界了。

那么為啥這個(gè)指針不能在作為容器的邊界了，下面是這個(gè)問題的證明：

首先考慮第一步，假設(shè)當(dāng)前左指針和右指針指向的數(shù)分別為 x 和 y，先假設(shè) x < y ，同時(shí)兩個(gè)指針之間的距離為 t ，那么他們組成的容器的容量為：

min(x,?y)?*?t?=?x?*?t

這時(shí)可以斷定，如果我們保持左指針的位置不變，那么無論右指針在哪里，這個(gè)容器的容量都不會(huì)超過 x * t 了。注意這里右指針只能向左移動(dòng)，因?yàn)槲覀兛紤]的是第一步，也就是指針還指向數(shù)組的左右邊界的時(shí)候。

我們?nèi)我獾囊苿?dòng)右指針，指向的數(shù)字為 y1 ，兩個(gè)指針之間的距離為 t1 ，那么顯然有 t1 < t ，并且 min(x, y1) <= min(x, y) 。

• 如果 y1 <= y 那么有 min(x, y1) <= min(x, y) 。
• 如果 y1 > y 那么有 min(x, y1) = x <= min(x, y) 。

因此剛才上面的那個(gè)公式可推導(dǎo)：

min(x,?y1)?*?t1?=?min(x,?y)?*?t?

即無論我們怎么移動(dòng)右指針，得到的容器的容量都小于移動(dòng)前容器的容量。也就是說，這個(gè)左指針對應(yīng)的數(shù)不會(huì)作為容器的邊界了，那么我們就可以丟棄這個(gè)位置，將左指針向右移動(dòng)一個(gè)位置，此時(shí)新的左指針于原先的右指針之間的左右位置，才可能會(huì)作為容器的邊界。

這樣以來，我們將問題的規(guī)模減小了 11，被我們丟棄的那個(gè)位置就相當(dāng)于消失了。此時(shí)的左右指針，就指向了一個(gè)新的、規(guī)模減少了的問題的數(shù)組的左右邊界，接下來，我們可以重復(fù)上面的這個(gè)過程，接著縮小容器邊界。

---

感謝閱讀

總結(jié)

以上是生活随笔為你收集整理的leetcode最小面积_每日一道 LeetCode (51)：盛最多水的容器的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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