本文共 1741 字，大约阅读时间需要 5 分钟。

DESC1:

给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 1。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的直方图，在这种情况下，可以接 6 个单位的水（蓝色部分表示水）。 感谢 Marcos 贡献此图。

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]

输出: 6

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/volume-of-histogram-lcci

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目描述2

给定一个整形数组arr，已知其中所有的值都是非负的，将这个数组看作一个容器，请返回容器能装多少水。

CODE1:

JAVA:

class Solution {    public int trap(int[] height) {        if (height == null || height.length<=2) {            return 0;        }        int left=0, right=height.length-1;        int mark = Math.min(height[left], height[right]);        int maxWater = 0;        while (left

 

NOTES1:

1. 双指针，分别指向左右边界，记录较小的边界为mark，即短板；
2. 从短板边界像里移动指针，当新指针值小于及矮于边界，意味着可存水，叠加差值，如果新指针值大于短板边界，意味着不能存水，同时更新短板值；
3. 每次从短板边界向里移动迭代即可；

DESC2:

给你 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 <= 3 * 104

    0 <= height[i] <= 3 * 104

来源：力扣（LeetCode）

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

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

CODE2:

JAVA:

class Solution {    public int maxArea(int[] height) {        if (height == null || height.length<=1) {            return 0;        }        int left=0, right=height.length-1;        int maxWater = 0;        while (left

 

NOTES2:

1. 注意和题一的不同，这里是在给定的数组中任意找两个板，看哪两个板中间存的水最多；
2. 双指针指向左右边界，找到短板边界，此时左右边界两个板可存的水为min(left,right)*(right-left)，即短板高度*两板距离；
3. 每次从短板那边开始往里靠，从新计算短板和存水量，并更新最大存水量
4. 为什么从短板往里靠，因为对于该短板，右边界已经是其能存的最大水量了，从用往里靠，距离变短了，所以该短板已经发挥万他的最大作用，可以丢弃了；