盛最多水的容器C语言和JAVA双指针解法

题目描述:

力扣链接:https://leetcode.cn/problems/container-with-most-water/description/

题意: 根据数组中的值(高)和下标差值(宽),求能容纳最多的体积V.

例子:

输出49的求解过程,根据木桶效应,存储水的高度由短木板决定,故 V = 短木板(高) * 下标差(宽) = 7 * 7 = 49

思路:使用双指针(一个放在右,一个放在左,可以减少时间复杂度),保证一个值不变化(即最大的数组元素),小的元素进行变化.通过考虑小的元素变化情况来减少求V次数.并使用一个变量记录改变后的V值,再与最大值进行比较,最后返回最大值即可.

解题步骤:

1.创建双指针,分别定义在左右下标.

2.求两个下标对应的V值,并与max进行比较.

3.固定值不变,改变最小值,再次进行步骤2.

4.循环结束,返回最大值.

C语言代码如下:

int maxArea(int* height, int heightSize) {//1.创建左右指针int left = 0;int right = heightSize - 1;int max = 0;int tmp = 0;//2.循环求体积V,并使用max进行记录while(left < right) {if(height[left] > height[right]) {tmp = height[right]  * (right - left);//存储Vright--;//right对应值为小元素,则right改变}else {tmp = height[left] * (right - left);left++;//同上}if(tmp >= max) {max = tmp;}}//3.判断左右下标值,保存最大的一个继续进行循环return max;
}

JAVA代码如下:

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