Leetcode 热题11.盛最多水的容器（c++，双指针详细解法及完整版代码）_leetcode盛水最多的容器c++

题目：11. 盛最多水的容器

给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

输入：height = [1,1]
输出：1

示例 3：

输入：height = [4,3,2,1,4]
输出：16

示例 4：

输入：height = [1,2,1]
输出：2

提示：

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

思路推荐官方解答如下：

力扣

核心思想：

容器体积：左右两端指针指向的数字中较小值∗指针之间的距离,即：min(left,right) * len

 移动规则：保持一端的指针指不变，每次移动指向数值较小的指针一格

双指针解法1：

#include <iostream>
#include <vector>
#include <string>
using namespace std;
 
class Solution{
public:
	int maxArea(vector<int>& height) {
	//l是左端，r端开始，ans临时存放area，area每次计算出的容积 
	int l = 0, r = height.size() - 1 , ans = 0, area = 0;
	while (l < r){
		area = ( r - l ) *  min (height[l], height[r]);
		//一格指针移动后，取这次计算的area和上次计算的容积哪个大 
		ans = max(ans, area);
		if (height[l] < height[r]){
			l++;
		} else{
			r--;
		}
	}
	return ans;
	}
};
 
int main(){
	Solution solution;
    int res;
    vector<int > arr = {1,8,6,2,5,4,8,3,7};
    res = solution.maxArea(arr);
    cout << res << endl;
    return 0;
}

双指针解法2：

看到leetcode一个大神的写法，很简洁优美

力扣

#include <iostream>
#include <vector>
#include <string>
using namespace std;
 
class Solution{
public:
	int maxArea(vector<int>& height) {
	int l = 0, r = height.size() - 1 , ans = 0;
	while ( l < r){
		ans = height[l] < height[r] ?
			max(ans, (r - l ) * height[l++]):
			max(ans, (r - l ) * height[r--]);
	}
	return ans;
	}
};
 
int main(){
	Solution solution;
    int res;
    vector<int > arr = {1,8,6,2,5,4,8,3,7};
    res = solution.maxArea(arr);
    cout << res << endl;
    return 0;
}