LeetCode题解-11-Container With Most Water

2019-11-06 07:27:54

字体：大中小

来源：转载

供稿：网友

解题思路

题意是说，有一堆有序的数字ai，要计算min(ai,aj)*abs(i-j)的最大值，普通的算法就是列举所有的情况，时间复杂度是O(n^2)。下面介绍一下O(n)的思路。

首先记录左边是left,右边是right，那么初始化max就是左右两边组成的值。

假设左边比较小。

如果left+i比left的值要小，那么由left+i和right组成的值会更小，而left和left+1组成的值也是更小的。如果left+i比left的值要大，那么由left+i和right组成的值可能会更大或更小，而left和left+1组成的值是更小的。那么就可以从左边渐进一个位置，直到找到一个left+i的值比left要大，让值和max去比较。右边较小的情况是类似的，最终left会超过right，这个时候就结束了。

参考源码

public class Solution { public int maxArea(int[] height) { int max = 0; if (height == null || height.length < 2) { return max; } int left = 0; int right = height.length - 1; while (left < right) { int tmax = (right - left) * Math.min(height[left], height[right]); if (tmax > max) { max = tmax; } if (height[left] < height[right]) { int t = left; while (t < right && height[t] <= height[left]) { t++; } left = t; } else { int t = right; while (t > left && height[t] <= height[right]) { t--; } right = t; } } return max; }}

上一篇：Ubuntu16.04编译Caffe遇到的问题及解决办法

下一篇：Leetcode-8. String to Integer (atoi)