Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit479a42f

Browse files
committed
Create ContainerWithMostWater.java
This is a classic problem that is solved by using two-pointer technique. The problem states as follows: 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. You may not slant the container.To start with, we use two pointers to point at the left and right boundary of the container, one at leftmost index and the other at rightmost index as an initial step, respectively. The strategy is keep moving two pointers (boundaries) closer to each other until they meet. During the moving procedure, we keep calculating the container size. The trick here is how to move the two pointers so that we can do it in one pass and more over skip as many indices as possible.Suppose we have the following height array and the left and right pointers are at `lo` and `hi`, respectively. | *** | | | *** | | | | | *** | | | | | | | *** | | | | | | | *** | | | | | | | | | *** | | | | | | | | | *** | | | | | | | | | | *** | | | | | | | | | | | *** | | | | | | lo @ hiWe first compute the container size with `(lo, hi)` pair and update the final `max` size if the computed result is greater than current `max`.Also, in this scenario, `height[lo] > height[hi]`, we claim the following important fact: - when `height[lo] > height[hi]`, if `hi` is the right line that forms the largest container, all lines to the right of `lo` cannot be the left line of the largest container. This is actually quite easy to show, since size = height[hi] * (hi-lo),if `lo` increases, `size` will reduce for sure. This fact is critical, because we can skip all other indices for `lo` under this particular `hi` and safely move `hi` to `hi-1` and continue.When `hi` moves left a step, we notice that `height[lo] < height[hi]`. Similar as above, we can safely skip all indices to the left of `hi` under this particular `lo`. That is, we can move `lo` to `lo+1` and continue.However, this is not the most optimized solution yet.Suppose `hi` moves to `@` as indicated in the above figure, we notice that its value is greater than its right neighbor, so we will not skip that one according to the above analysis. But do we really need to consider `@` as a candidate?The answer is no. Because `@` has a value no greater than `hi` in the above figure. So `@` cannot be the right index of the largest container. (If it is, why don't we choose `hi` and get a larger container?) Therefore, to further optimize the algorithm, I store two local variables `loMax` and `hiMax`, that is the max value of all items to `lo`'s left and `hi`'s right, respectively. We can then skip `@` because `height[@] <= hiMax`.
1 parente8dcf29 commit479a42f

File tree

1 file changed

+30
-0
lines changed

1 file changed

+30
-0
lines changed
Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
publicclassContainerWithMostWater {
2+
3+
publicintmaxArea(int[]height) {
4+
intL=height.length,lo =0,hi=L-1;
5+
if(L<2)return0;
6+
intmax =0;
7+
while(lo<hi) {
8+
intloMax =height[lo],hiMax =height[hi];
9+
10+
intcandidate = (hi-lo) * (loMax<hiMax ?loMax :hiMax);
11+
max =candidate >max ?candidate :max;
12+
13+
if(height[lo]<=height[hi])
14+
while(lo<L-1 &&height[lo]<=loMax) ++lo;
15+
else
16+
while(hi>0 &&height[hi]<=hiMax) --hi;
17+
}
18+
returnmax;
19+
}
20+
21+
publicstaticvoidmain(String[]args) {
22+
ContainerWithMostWaterq =newContainerWithMostWater();
23+
24+
int[]height = {5,2,12,1,5,3,4,11,9,4};
25+
26+
intres =q.maxArea(height);
27+
28+
System.out.println(res);
29+
}
30+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp