LeetCode 11.盛最多水的容器
目录
题目:
题目描述:
题目链接:
思路:
核心思路:
思路详解:
代码:
Java代码:
C++代码:
题目:
题目描述:
题目链接:
11. 盛最多水的容器 - 力扣(LeetCode)
思路:
核心思路:
双指针
思路详解:
这题主要是用双指针的思想来解决,首先定义area用于记录所有情况中的最大容量,i指针指向数组第一个元素,j指针指向数组最后一个元素。由题及常识不难理解容器的最大容量取决于短板,如果当前情况是i指向的是短板,那我们就需要尝试去寻找更长的板,所以j指向的长板不用动将i指针后移。如果当前情况是j指向的是长板,那我们也同样需要尝试去寻找更长的板,所以i指向的长板不用动将j指针前移。双指针合法的条件就是i<j,因为i==j的时候底就为0了,i>j实际上就和i<j的情况重复了
代码:
Java代码:
class Solution { //双指针public int maxArea(int[] height) {int area = 0; //area用于记录所有情况中的最大容量int i = 0; //i指针指向数组第一个元素int j = height.length - 1; //j指针指向数组最后一个元素int s,h;while(i < j){h = Math.min(height[i],height[j]); //此时容器的最大容量取决于短板s = h * (j - i); //计算此时容器的最大容量if(s > area) //如果出现更大的容量就修改area记录的数值{area = s;}if(height[i] < height[j]) //如果i指向的是短板就i指针后移去寻找更长板{i++;}else //如果j指向的是短板就j指针前移去寻找更长板{j--;}}return area;}
}
C++代码:
class Solution { //注释同理Java代码
public:int maxArea(vector<int>& height) {int area = 0;int i = 0;int j = height.size() - 1;int s,h;while(i < j){h = min(height[i],height[j]);s = h * (j - i);if(s > area){area = s;}if(height[i] < height[j]){i++;}else{j--;}}return area;}
};