摘要:一題目盛最多水的容器給定個非負整數,,,,每個數代表坐標中的一個點。在坐標內畫條垂直線,垂直線的兩個端點分別為和。找出其中的兩條線,使得它們與軸共同構成的容器可以容納最多的水。在此情況下,容器能夠容納水表示為藍色部分的最大值為。
一、題目
盛最多水的容器:
給定 n 個非負整數 a1,a2,...,an,每個數代表坐標中的一個點?(i,?ai) 。在坐標內畫 n 條垂直線,垂直線 i?的兩個端點分別為?(i,?ai) 和 (i, 0)。找出其中的兩條線,使得它們與?x?軸共同構成的容器可以容納最多的水。說明:你不能傾斜容器,且?n?的值至少為 2。
圖中垂直線代表輸入數組 [1,8,6,2,5,4,8,3,7]。在此情況下,容器能夠容納水(表示為藍色部分)的最大值為 49。二、我的答案
???????首先分析一下題目,與接雨水那道題不同的是,本題所求為“找出其中的兩條線,使得它們與?x?軸共同構成的容器可以容納最多的水”, 也就是說[6,7,6]這樣的數組,最多接水的兩條線的下標為0和2。同時也可以看出這道題與最大值無關,計算公式應該是Math.min(height[head], height[tail]) * (tail - head),head和tail都出來,雙指針不要太明顯
???????因為每次接水面積的高是兩個指針中指向的值較小的那個,所以為了求最大值,我們每次向中間移動的指針也應該是辣一個,思路理清,代碼如下
/** * @param {number[]} height * @return {number} */ var maxArea = function(height) { let tail = height.length - 1, head = 0; let container = 0, temp; while(head < tail) { temp = (tail - head) * Math.min(height[head], height[tail]) container < temp ? container = temp : null if(height[head] < height[tail]) { head++ } else { tail-- } } return container };
???????
三、優秀答案/** * @param {number[]} height * @return {number} */ var maxArea = function(height) { let i = 0; let j = height.length - 1; let max = 0 while(iheight[j]) { j-- } else { i++ } } return max };
???????取最大值使用max = Math.max((j - i) * min), max)還是非常秀的
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/105784.html
摘要:我們需要找出這些線所圍成的容器,能裝最多水的水量。這道題是不能用蠻力法解決的,會超時。這個解法想法是這樣的,我們用兩個變量,指向數組的起始元素和末尾元素。首先計算這兩條線所圍成的容器面積,然后移動指向較短的線段的指針。 題目詳情 Given n non-negative integers a1, a2, ..., an, where each represents a point at...
摘要:盛最多水的容器給定個非負整數,,,,每個數代表坐標中的一個點。在坐標內畫條垂直線,垂直線的兩個端點分別為和。找出其中的兩條線,使得它們與軸共同構成的容器可以容納最多的水。在此情況下,容器能夠容納水表示為藍色部分的最大值為。 LeetCode11.盛最多水的容器 JavaScript 給定 n 個非負整數a1,a2,...,an,每個數代表坐標中的一個點 (i, ai) 。在坐標內畫 n...
摘要:題目要求給一個數組,其中數組在下標處的值為,坐標和坐標構成一條垂直于坐標軸的直線。現任取兩條垂線和軸組成四邊形容器。當左右指針相遇時,指針假設該算法并沒有遍歷到容量最大的情況我們令容量最大時的指針為和。 題目要求:給一個數組,其中數組在下標i處的值為A[i],坐標(i,A[i])和坐標(i,0)構成一條垂直于坐標軸x的直線?,F任取兩條垂線和x軸組成四邊形容器。問其中盛水量最大為多少? ...
摘要:一題目描述空格分隔,逐個反轉二題目描述三題目描述當然也可以用的做,不過用雙指針更快。 LeetCode: 557. Reverse Words in a String III 一、LeetCode: 557. Reverse Words in a String III 題目描述 Given a string, you need to reverse the order of chara...
摘要:分布式的管理和當我在談論架構時我在談啥狀態碼詳解無狀態協議和請求支持哪些方法分層協議棧有哪些數據結構運用場景說說你常用的命令為什么要有包裝類面向對象的特征是啥是啥有什么好處系統設計工程在線診斷系統設計與實現索引背后的數據結構及算法原理軟技能 HTTP 【HTTP】分布式session的管理 【HTTP】Cookie和Session 【HTTP】當我在談論RestFul架構時我在談啥?...
閱讀 2368·2021-11-18 10:07
閱讀 2318·2021-09-22 15:59
閱讀 3077·2021-08-23 09:42
閱讀 2276·2019-08-30 15:44
閱讀 1191·2019-08-29 15:06
閱讀 2303·2019-08-29 13:27
閱讀 1210·2019-08-29 13:21
閱讀 1412·2019-08-29 13:13