题目解析

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 and n is at least 2.

给出一系列a(i),任意两个(i, ai) and (i, 0) 和x轴组成的u型矩形面积最大,u型的两边长度可能不一致,所装容量为短板边长决定

分析

1、决定u型桶高度的是短板
2、决定面积的是x轴底边和上面所提到的短板边
3、O(n)负复杂度来处理问题,上一情况下,最短边调整,才会可能出现面积较大的场景。 那么采用两边夹逼

代码演示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
* Created by dylan on 2017/9/21.
* 两个边的构成一个矩形,为初始面积, 比它面积大的只可能是短边被替换,因为delta X变小,如果出现面积更大,只可能是比短边更长的边
* 例如图例中最大面积为a2和a4组成的u型矩形 面积为2*2=4
* a3
* a2 | a4
* a1 | | |
* | | | |
* ----------------
*/
public class A11MostContainer {
public int maxArea(int[] height) {
int max = 0;
int left = 0;
int right = height.length - 1;
while (left <= right) {
int minHeight = height[left] < height[right] ? height[left] : height[right];//u型桶的短板, 最小竖边
int curr = (right - left) * minHeight;
max = max > curr ? max : curr;
if (height[left] < height[right]) { // 逻辑思路是最短边变化才会出现面积更大的u型桶
left++;
} else {
right--;
}
}
return max;
}
public static void main(String[] args) {
A11MostContainer a11MostContainer = new A11MostContainer();
System.out.println(a11MostContainer.maxArea(new int[]{1, 2, 3, 2}));
}
}

代码文件:
A11MostContainer.java

总结

  • 如果能想到这个思路,解题较简单, “逻辑思路是最短边变化才会出现面积更大的u型桶”。

版权声明:本文为博主原创文章,未经允许不得转载。