leetcode------Container With Most Water

3771 단어 LeetCode
제목:
Container With Most Water
통과율:
31.9%
난이도:
중간
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.
Note: You may not slant the container.
이 문제는 가장 큰 면적의 장방형을 찾는 것이다. 공식은min(h(l), h(r))*(r-l)이다
그러면 틀림없이 양쪽에서 안쪽으로 찾을 것이다. 예를 들면:
만약 h(l)반대로 뒤에서 h(r)보다 큰 것을 찾아서 다시 계산하면
매번 계산할 때마다result를 한 번 업데이트해야 하는데, 마지막result가 틀림없이 가장 큰 것이다
코드는 다음과 같습니다.
 1 public class Solution {

 2     public int maxArea(int[] height) {

 3         int l=0,r=height.length-1,result=0;

 4         while(l<r){

 5             result=Math.max(result,Math.min(height[l],height[r])*(r-l));

 6             if(height[l]<height[r]){

 7                 int k=l;

 8                 while(k<r&&height[k]<=height[l]){

 9                     k++;

10                 }

11                 l=k;

12             }

13             else{

14                 int k=r;

15                 while(k>l&&height[k]<=height[r]){

16                     k--;

17                 }

18                 r=k;

19             }

20         }

21         return result;

22     }

23 }

 

좋은 웹페이지 즐겨찾기