摘要:軸上兩指針的距離為矩形長軸取兩個指針?biāo)傅妮^短邊作為寬,相乘所得為最大裝水容量。將兩指針向中間移動,更新的最大值。
Problem
Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
ExampleGiven [1,3,2], the max area of the container is 2.
NoteX軸上兩指針的距離right - left為矩形長;
Y軸取兩個指針?biāo)傅妮^短邊:
Math.min(heights[left], heights[right])作為寬,相乘所得max為最大裝水容量。將兩指針向中間移動,更新max的最大值。
參考:
https://segmentfault.com/a/1190000003815582
public class Solution { public int maxArea(int[] heights) { // write your code here int left = 0, right = heights.length - 1, max = 0; while (left < right) { max = Math.max(max, Math.min(heights[left], heights[right]) * (right - left)); if (heights[left] < heights[right]) left++; else right--; } return max; } }
文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址:http://systransis.cn/yun/65514.html
摘要:思路對撞指針問題,求最大體積,當(dāng)縮小寬度時,則高度必須比原來大。兩邊指針選較小的一個靠近直到比原來的大。此程序?qū)崿F(xiàn)中省略了內(nèi)層。 http://www.lintcode.com/en/pr... Container with Most Water Given n non-negative integers a1, a2, ..., an, where each represents ...
摘要:最新更新請訪問棧法復(fù)雜度時間空間思路最大盛水量取決于兩邊中較短的那條邊,而且如果將較短的邊換為更短邊的話,盛水量只會變少。所以我們可以用兩個頭尾指針,計算出當(dāng)前最大的盛水量后,將較短的邊向中間移,因為我們想看看能不能把較短的邊換長一點。 Container With Most Water 最新更新請訪問:https://yanjia.me/zh/2018/11/... Given n...
摘要:題目解答這里如果左邊的數(shù)比右邊的數(shù)小,那么這就是取這個位置時的面積最大值。因為不管怎么向左移動,最大高度也還是的值,而寬只會減小。所以我們只有向右移動才有可能遇到更大的,從而有可能產(chǎn)生更大的面積。 題目:Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (...
摘要:我們需要找出這些線所圍成的容器,能裝最多水的水量。這道題是不能用蠻力法解決的,會超時。這個解法想法是這樣的,我們用兩個變量,指向數(shù)組的起始元素和末尾元素。首先計算這兩條線所圍成的容器面積,然后移動指向較短的線段的指針。 題目詳情 Given n non-negative integers a1, a2, ..., an, where each represents a point at...
摘要:一題目盛最多水的容器給定個非負(fù)整數(shù),,,,每個數(shù)代表坐標(biāo)中的一個點。在坐標(biāo)內(nèi)畫條垂直線,垂直線的兩個端點分別為和。找出其中的兩條線,使得它們與軸共同構(gòu)成的容器可以容納最多的水。在此情況下,容器能夠容納水表示為藍(lán)色部分的最大值為。 一、題目 盛最多水的容器: 給定 n 個非負(fù)整數(shù) a1,a2,...,an,每個數(shù)代表坐標(biāo)中的一個點?(i,?ai) 。在坐標(biāo)內(nèi)畫 n 條垂直線,垂直線 i?...
閱讀 3059·2023-04-26 03:01
閱讀 3547·2023-04-25 19:54
閱讀 1600·2021-11-24 09:39
閱讀 1382·2021-11-19 09:40
閱讀 4262·2021-10-14 09:43
閱讀 2099·2019-08-30 15:56
閱讀 1504·2019-08-30 13:52
閱讀 1669·2019-08-29 13:05