一、题目二、解析1.基本思路首先搞清楚最基本的解题思路。要求“最大储水量”把每一种情况的储水量算出来遍历所有情况即可。那么怎么算储水量呢容积底×高Vs*h注意此处的h是当前区间左右端点的较小值若将区间命名为 [left , right]则 sright - left , h min (height [left] , height[right])。使用最基础的遍历解法如图从左到右进行遍历即可。操作次数形成等差数列易知时间复杂度为O(n^2)。是否有规律可以减少时间复杂度2.寻找规律滑动窗口找单调性**本题的两个特点1.高是两区间端点的较小值 2.操作对象是连续的多个单位区间连续变化时具有单调性。先说第一个特点如上图以0为固定点进行遍历时假设最开始0处值较小hheight[0]若从左向右遍历则有两种情况。区间变化后当右端点的值较大时hheight[0]若右端点值较小则hheight[right]注意此时hheight[0]。若连续出现情况一则随着从左向右遍历底s变大V就变大若连续出现情况二随着从左向右遍历虽h变小但s变大无法判断V的变化。此时结合上第二个特点由于操作对象是连续的多个单位区间连续变化时具有单调性。起初采用“扩大区间”即区间从左向右扩张使s单调递增。但由于h在变化过程中是非严格递减的故单调递增的s不利于V的单调性的形成。倘若我们采用“缩小区间”遍历的方法则s单调递减配合上h的非严格单调递减则V就形成了“非严格单调递减”的单调性注意“最开始h为0处的值”这一点非常重要只有以较小值端点为固定点才能形成单调性。若一开始7处值较小则h最开始为height[7]若此时区间由[0,7]变化为[0,6]则hheight[0]或者height[6]此时已知“ height[0] height[7] ”若现在hheight[0]则s变小但h变大若hheight[6]即“ height[0] height[6] ”但无法确定height[6]和height[7]的大小关系故V不一定由单调性。总结区间收缩时一定要以值较小的端点为固定点。综上我们进行缩小区间的遍历方法。从[0,7]开始右端点内收s递减。如前面的分析一样若初始右端点值较大则hheight[0]。之后收缩的过程中s一定减小h不变或者减小故V一定非严格单调递减。以0为固定点进行遍历时V一定非严格单调递减意味着V一定不会增大故实际上当我们采用“收缩区间”遍历的方法时若最开始hheight[0]则区间为[0,7]时的体积就是“左端点为0”时所有情况中V最大的时候。所以我们只要计算出区间为[0,7]时的V并记录下来即可此时“左端点为0”的所有情况就相当于遍历完了故将区间左端点右移变成1进入下一轮的判断。假设height[1] height[7]按照前面的规律可知此时应以7为固定点重复之前的规律。我们之前是以”从右向左收缩“为例子进行推断的这里从左向右收缩的时候规律还适用吗没问题二者实质上等价。例如此时0的情况已遍历完成我们可以直接忽略0处的元素将[1,7]看成一个新数组此时这个数组可以随意翻转将[1,7]翻转成[7,1]之后即将进行的从左向右收缩1收缩就变成了从右向左收缩。综上这个规律适用于所有”收缩遍历“的区间。故区间应变成[1,6]。不断重复直到左右端点重合所有情况就遍历完成。易知时间复杂度为O(n)。3.优化解法”获得区间 [left,right]找到两端点的就较小值作为固定点并计算当前的V与Vmax进行比较、更新 --- 根据固定点缩小区间“不断重复该过程直到 left right即可。三、代码class Solution { public: int maxArea(vectorint height) { int left0,rightheight.size()-1,ret0; while(leftright) { int hmin(height[left],height[right]); int wright-left; int vh*w; retmax(ret,v); if(hheight[left]) left; else --right; } return ret; } };