摘要:軸上兩指針的距離為矩形長軸取兩個(gè)指針?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軸取兩個(gè)指針?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://specialneedsforspecialkids.com/yun/65514.html
摘要:思路對撞指針問題,求最大體積,當(dāng)縮小寬度時(shí),則高度必須比原來大。兩邊指針選較小的一個(gè)靠近直到比原來的大。此程序?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 ...
摘要:最新更新請?jiān)L問棧法復(fù)雜度時(shí)間空間思路最大盛水量取決于兩邊中較短的那條邊,而且如果將較短的邊換為更短邊的話,盛水量只會變少。所以我們可以用兩個(gè)頭尾指針,計(jì)算出當(dāng)前最大的盛水量后,將較短的邊向中間移,因?yàn)槲覀兿肟纯茨懿荒馨演^短的邊換長一點(diǎn)。 Container With Most Water 最新更新請?jiān)L問:https://yanjia.me/zh/2018/11/... Given n...
摘要:題目解答這里如果左邊的數(shù)比右邊的數(shù)小,那么這就是取這個(gè)位置時(shí)的面積最大值。因?yàn)椴还茉趺聪蜃笠苿樱畲蟾叨纫策€是的值,而寬只會減小。所以我們只有向右移動才有可能遇到更大的,從而有可能產(chǎn)生更大的面積。 題目:Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (...
摘要:我們需要找出這些線所圍成的容器,能裝最多水的水量。這道題是不能用蠻力法解決的,會超時(shí)。這個(gè)解法想法是這樣的,我們用兩個(gè)變量,指向數(shù)組的起始元素和末尾元素。首先計(jì)算這兩條線所圍成的容器面積,然后移動指向較短的線段的指針。 題目詳情 Given n non-negative integers a1, a2, ..., an, where each represents a point at...
摘要:一題目盛最多水的容器給定個(gè)非負(fù)整數(shù),,,,每個(gè)數(shù)代表坐標(biāo)中的一個(gè)點(diǎn)。在坐標(biāo)內(nèi)畫條垂直線,垂直線的兩個(gè)端點(diǎn)分別為和。找出其中的兩條線,使得它們與軸共同構(gòu)成的容器可以容納最多的水。在此情況下,容器能夠容納水表示為藍(lán)色部分的最大值為。 一、題目 盛最多水的容器: 給定 n 個(gè)非負(fù)整數(shù) a1,a2,...,an,每個(gè)數(shù)代表坐標(biāo)中的一個(gè)點(diǎn)?(i,?ai) 。在坐標(biāo)內(nèi)畫 n 條垂直線,垂直線 i?...
閱讀 3035·2023-04-26 03:01
閱讀 3538·2023-04-25 19:54
閱讀 1592·2021-11-24 09:39
閱讀 1374·2021-11-19 09:40
閱讀 4250·2021-10-14 09:43
閱讀 2062·2019-08-30 15:56
閱讀 1490·2019-08-30 13:52
閱讀 1660·2019-08-29 13:05