題目描述

給定一個(gè)長(zhǎng)度為 n 的整數(shù)數(shù)組 height 。有 n 條垂線，第 i 條線的兩個(gè)端點(diǎn)是 (i, 0) 和 (i, height[i]) 。

找出其中的兩條線，使得它們與 x 軸共同構(gòu)成的容器可以容納最多的水。

返回容器可以?xún)?chǔ)存的最大水量。

說(shuō)明：你不能傾斜容器。

題目

題目解答

這道題使用的是貪心算法，使用了雙指針

思路比較難想，代碼很簡(jiǎn)單

首先，我們讓距離最遠(yuǎn)的兩條線成為容器壁

隨后，找到高度較小的線，向內(nèi)找到相鄰的下一條線

記錄最大值，直到兩條線重合

十分的簡(jiǎn)單o((>ω< ))o

細(xì)節(jié)

為什么可以采用雙指針呢(⊙_⊙)？

假定左指針不移動(dòng)，只向左移動(dòng)右指針

這樣是不是容器的容量只會(huì)變小不會(huì)變大?。?/p>

好吧......

假如右指針變大了，但是左指針沒(méi)有變

而二者的距離變小了

所以容量變小了

假如右指針變小了，距離也變小了

容量當(dāng)然變小了

現(xiàn)在讓兩個(gè)指針都動(dòng)起來(lái)

如果挪動(dòng)大的，那么只能變小

但是如果挪動(dòng)小的，有可能變大

代碼

復(fù)雜度分析

時(shí)間復(fù)雜度：O(n)

空間復(fù)雜度：O(1)