本文共 2856 字,大约阅读时间需要 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 and n is at least 2.
The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
Example:
Input: [1,8,6,2,5,4,8,3,7]Output: 49
给定 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明:你不能倾斜容器,且 n 的值至少为 2。
图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。
示例:
输入: [1,8,6,2,5,4,8,3,7]输出: 49
class Solution { public int maxArea(int[] height) { int left = 0, right = height.length - 1; int max = 0; while (left < right) { int h = Math.min(height[left], height[right]); // 最短木板决定体积 int l = right - left; // 长度 int v = h * l; // 符合题意的平面体积 max = Math.max(max, v); if (height[left] < height[right]) { ++left; } else { --right; } } return max; }}
Debug code in playground:
class Solution { public int maxArea(int[] height) { int left = 0, right = height.length - 1; int max = 0; while (left < right) { int h = Math.min(height[left], height[right]); int l = right - left; int v = h * l; max = Math.max(max, v); if (height[left] < height[right]) { ++left; } else { --right; } } return max; }}public class MainClass { public static int[] stringToIntegerArray(String input) { input = input.trim(); input = input.substring(1, input.length() - 1); if (input.length() == 0) { return new int[0]; } String[] parts = input.split(","); int[] output = new int[parts.length]; for(int index = 0; index < parts.length; index++) { String part = parts[index].trim(); output[index] = Integer.parseInt(part); } return output; } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String line; while ((line = in.readLine()) != null) { int[] height = stringToIntegerArray(line); int ret = new Solution().maxArea(height); String out = String.valueOf(ret); System.out.print(out); } }}
==========================Talk is cheap, show me the code========================
转载地址:https://liuchenyang0515.blog.csdn.net/article/details/82965516 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!