LeetCode. Container With Most Water
3189 ワード
試験問題の概要
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個の点が与えられ、このn個の点の座標はすべてx軸の上にあり、x軸に垂線セグメントを作るとx本のセグメントが得られるということである.その中から2本の線分を選択する、この2本の線分とx軸とで形成されたシリンダの面積が最大となるようにする.
問題を解く構想.
最も簡単で乱暴な方法はこのn 22種類の組み合わせを貧乏に挙げることであり、考えなくても妥当なTLEを知っている.
2つのポインタi,j.iが一番左側から、jが一番右側からあるとする.シリンダの高いは両者のうちの小さい値によって決まるからである.height[i]
ソースコード
public class Solution {
public int maxArea(int[] height) {
int i = 0, j = height.length - 1;
int maxArea = getArea(height, i, j);
while ( i < j ) {
if ( height[i] < height[j] ) {
++ i;
} else {
-- j;
}
int currentArea = getArea(height, i, j);
if ( currentArea > maxArea ) {
maxArea = currentArea;
}
}
return maxArea;
}
private int getArea(int[] height, int i, int j) {
int a = Math.min(height[i], height[j]);
int b = j - i;
return a * b;
}
public static void main(String[] args) {
Solution s = new Solution();
int[] height = {2, 3, 10, 5, 7, 8, 9};
System.out.println(s.maxArea(height));
}
}