11. 盛最多水的容器

题目描述

给你一个数组，数组的每个数字表示每个板子的高度，相邻的2个板子之间的距离为1。

问任意2个板子之间最大的盛水量。

解题思路

首先我们想到暴力的解法，把所有的两个柱子可以盛水的容量都计算出来，显然时间复杂度是O(N^2)的。

那么我们如何降低时间复杂度快速的求出结果呢？

在暴力的时候，我们是固定一个，移动其他的。

假设i=2，j=10。固定i，遍历j。

假设nums[i]<nums[j]，sum=min(nums[i],nums[j])*t

j往左移动，sum=min(nums[i],nums[j1])*t1。

t1<t,min(nums[i],nums[j1])<min(nums[i],nums[j])。所以在nums[i]<nums[j]的情况下，j不需要遍历，直接舍弃就行，因为最优解在边界。

同理，nums[i]>nums[j]，i不需要遍历，直接舍弃就行，因为最优解在边界。

所以在暴力的基础上进行优化，固定大的一边，小的移动。（这就是双指针）

代码

class Solution {
public:
    int maxArea(vector<int>& height) {
        int sum=0;
        int n=height.size();
        int left=0,right=n-1;
        while(left<right)
        {
            sum=max(sum,(right-left)*min(height[left],height[right]));
            if(height[left]>height[right]) right--;
            else left++;
        }
        return sum;
    }
};