難度: Medium
類型: String, Two Pointers, Greedy,
前情題要:
容納最多水的容器。 左右個一個桿子, 較矮的那個桿子高度, 乗上兩個桿子的距離, 就是能容納的水量。
思考方式:
這題沒想到好方法前一直Time Limit Exceeded, 想到方法後就很簡單。Two Pointers, 一個在最左, 一個在最右, 然後算出容積。如果哪邊桿子比較矮, 就把那邊的桿子向中間移動, 尋找更高的桿子。如果兩邊一樣高, 就一起往內找更高的桿子。
1. 用python寫, 純粹是誤以為線上面試要改用python。後來確認後, 其他題又改回 C++ 來 coding 了。
2. 11_1.py, 跟 11_2.py 剛好可以拿來對比。11_1.py 一次向內移動一格, 而 11_2.py 是往內移動到更高的桿子為止。時間上從 11_1.py 花費 39ms, 進步到 11_2.py 花費 25ms。但我覺得差異不大。
複雜度思考:
Time Complexity: O( list length n )
Space Complexity: O( 1 )
結果:
Runtime: 25 ms, Beats: 98.01%
Memory: 24.51 MB, Beats: 24.01%
