.给定一个非负数的数组,代表一个容器。例如数组[0,1,0,2,1,0,1,3,2,1,2,1],就是
以下图形中黑色的部分。如果用这个容器接水的话,请问可以接多少水?还以这个数组为例, 可以接6格水,就是以下图形中蓝色的部分。 要求:实现时间复杂度O(N),额外空间复杂度O(1)的解法

注:因为没地方提交,所以只写思路了QAQ

做法:首先要注意的是,围出水的体积(面积)是总体的和,而不是像上一篇中的找最大面积。准备L,R两个指针分别放在最左边+1和最右边-1(因为最左和最右的位置少一个边框存水啊),维护左指针左侧的最大值leftmax,和右指针右侧的最大值rightmax,每次比较两个指针上指的值,选择小的向中间移动,两个指针遍历的过程中更新leftmax,rightmax。每个位置上的水量就是那一侧目前的max减去这个位置得数值。

2017.5.30终于在leeetcode上见到这个题了,居然是hard难度,总共不到20行的代码让我觉得自己mdzz

早上的时候比较纠结为啥一定会以短的那边为准,难道不可能短的里面出现更短的么……然后画图举例子发现自己sb了,整个水槽是一个整体,一定是从两边开始比较的

class Solution {
public:
    int trap(vector<int>& height) {
        int sum=0;
        int l=0,r=height.size()-1;
        while(l<r)
        {
            int minh=min(height[l],height[r]);
            if(minh==height[l])
                while(++l<r&&height[l]<minh)
                    sum+=minh-height[l];
            else
                while(l<--r&&height[r]<minh)
                    sum+=minh-height[r];
        }
        return sum;
    }
};



.给定一个非负数的数组,数组中的每个值代表一个柱子的高度,柱子的宽度是1。两个柱
子之间可以围成一个面积,规定:面积=两根柱子的最小值*两根柱子之间的距离。比如数 组[3,4,2,5]。3和4之间围成的面积为0,因为两个柱子是相邻的,中间没有距离。3和 2之间围成的面积为2,因为两个柱子的距离为1,且2是最短的柱子,所以面积=1*2。3和5之间围成的面积为6,因为两个柱子的距离为2,且3是最短的柱子,所以面积= 3*2。求在一个数组中,哪两个柱子围成的面积最大,并返回值。 要求:实现时间复杂度O(N),额外空间复杂度O(1)的解法

做法:这个题和上一篇的不一样,并不要求两个边界的值小于等于中间夹着的数值!所以按着双指针的思路,一个在左侧,一个在右侧,若左侧的指针上的数小,左指针向中间移动,反之亦然。为什么?右侧的数字大,要是再移动右边的指针,高度最小值不变,但是长度会减少!