By yusijia

Updated:

Contents
  1. 1. 题意：
  2. 2. 思路：
1
2
3
4
5
6
7
8
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.
 */

题意：

　　给定n个非负整数a1,a2,…,an，其中每个代表一个点坐标（i,ai）。 n个垂直线段例如线段的两个端点在（i,ai）和（i,0）。 找到两个线段，与x轴形成一个容器，使其包含最多的水。 备注：你不必倾倒容器。

思路：

　　从两侧向中间逼近，一开始就使底的宽度最宽，然后向中间变小的时候去找线段更长的情况，同时记录最大值

  • 同样的思路，用java提交超时了，C++过了…… 写算法题还是用C++写吧…
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public int maxArea(int[] height) {
        int L = 0, R = height.length - 1;
        int area = 0;
        while(L < R){
            area = Math.max(area, (R - L) * Math.min(height[L], height[R]));
            if(height[R] > height[L]){
                L++;
            }else{
                R--;
            }
        }
        return area;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int maxArea(vector<int>& height) {
        int L = 0, R = height.size() - 1;  
        int area = 0;  
        while (L < R) {  
            area = max(area, min(height[L], height[R]) * (R - L));  
            if (height[L] > height[R])  
                R--;  
            else  
                L++;  
        }  
        return area;  
    }
};
Contents
  1. 1. 题意：
  2. 2. 思路：