盛最多水的容器

傷城~ 2022-12-08 15:43 163阅读 0赞

# 盛最多水的容器 #

## 1、参考资料 ##

https://leetcode-cn.com/problems/container-with-most-water/

## 2、题目要求 ##

> 题目描述

![image-20200919130824790][]

> **示例：**

输入：[1,8,6,2,5,4,8,3,7]
    输出：49

## 3、代码思路 ##

双指针

1.  本题是一道经典的面试题，最优的做法是使用「双指针」，我们从题目给的示例一步一步推导双指针的过程
2.  题目中的示例数组为 `[1,8,6,2,5,4,8,3,7]`，我们定义两个指针：`leftPointer` 和 `rightPointer`，在初始化时，`leftPointer` 指向数组的第一个元素，`rightPointer` 指向数组的最后一个元素
3.  我们希望盛越多的水越好，无非就是尽量满足如下两个条件：一是容器的底越宽越好(即 `rightPointer-leftPointer` 越大越好)，二是容器的高度越高越好(即 `nums[leftPointer]` 和 `nums[rightPointer]` 围成的墙高越高越好)
4.  那么，我们最开始的时候让 `leftPointer` 指向数组的第一个元素，`rightPointer` 指向数组的最后一个元素，我们先让容器的底最宽，计算出此时的容器体积
5.  接着，我们试图减少容器的宽度，增高容器的高度，看看能不能得到更大的容器体积，和上一次相比，想要增加容器的高度，就只能改变低的墙，即移动指向较小数值的指针，才可能使得容器体积增加；否则，如果移动指向较大数值的指针，只能使得容器体积减小
6.  以此类推。。。

--------------------

下面的动图演示了整个算法的流程(来自 `LeetCode` 官方图解)

![image-20200920183114347][]

--------------------

为什么不能选择较小值作为容器的边界？

1.  双指针代表的是 可以作为容器边界的所有位置的范围。在一开始，双指针指向数组的左右边界。在这之后，我们每次将对应的数字较小的那个指针往另一个指针的方向移动一个位置，就表示我们认为这个指针不可能再作为容器的边界了。
2.  为什么呢？因为我们如果移动指向较大数值的指针，只会使得容器底边变窄，并且容器的高度永远不会超过上次的较小数值，这样只会导致容器体积往减小的方向发展
3.  读到一个企业级评论：感觉这个移动有点博弈论的味了，每次都移动自己最差的一边，虽然可能变得更差，但是总比不动（或者减小）强，动最差的部分可能找到更好的结果，但是动另一边总会更差或者不变，兄弟们，这不是题，这是人生，逃离舒适圈！！（这解释我觉得无敌了，哈哈哈）

## 4、代码实现 ##

代码

class Solution {
        
        public int maxArea(int[] nums) {
        
    
            int leftPointer = 0; // 初始化时 leftPointer 指向数组的第一个元素
            int rightPointer = nums.length - 1; // 初始化时 rightPointer 指向数组的最后一个元素
            int maxArea = 0; // 容器的最大体积为 0
    
            while (leftPointer < rightPointer) {
        
                // 容器的高度取 nums[leftPointer] 和 nums[rightPointer] 中的较小值
                // 每次计算完容器体积之后，移动移动指向较小数值的指针
                if (nums[leftPointer] < nums[rightPointer]) {
        
                    maxArea = Math.max(maxArea, nums[leftPointer] * (rightPointer - leftPointer));
                    leftPointer++;
                } else {
        
                    maxArea = Math.max(maxArea, nums[rightPointer] * (rightPointer - leftPointer));
                    rightPointer--;
                }
            }
    
            return maxArea;
        }
    }

[image-20200919130824790]: /images/20221123/09e27a54e80343899e4cf63e1757d7af.png
[image-20200920183114347]: /images/20221123/c2e3eac9f0394e89a734e2b2d7589655.png