算法刷题:盛水最多的容器

本文主要是介绍算法刷题:盛水最多的容器，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

.

习题链接

盛水最多的容器

题目

题目解析

V=H*W
h为左右两边低的一边,w为左右两边之间的距离

算法原理

定义两个指针
left=0,right=n-1;
left从左往右对数组进行遍历,right从右往左进行遍历
遍历的过程中,每一次都需要记录当前容器的体积
关键:
因为V=H*W,而w在遍历的过程中一直在减小,对于较小的一边来说,遍历的过程中,会出现两种结果:
假如最小的是左边,固定左边,遍历右边,会出现以下两种情况:

1. 假如遇到的值比之前的左边小,会导致h减小,从而使得v减小
2. 假如遇到的值比之前左边的大,甚至比右边的都大,但是对容器的高度h没有影响,因此,还是会使得v减小

因此,分析可以得出,固定高度低的一方,遍历的结果都是没有意义的,因此,我们只需要将其跳过就行,当前情况下,我们就可以使用left++,来跳过这个数
期间每次都需要计算当前的容量,直到left与right相遇,找到所有v中的最大值,就是题目的结果

我的答案

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

这篇关于算法刷题:盛水最多的容器的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---