盛最多水的容器题目描述先看清高度和宽度都重要为什么可以丢弃较短的那条边跟着例子走一遍代码里的变量表示什么C 实现C main调用C 实现C main调用复杂度与易错点这套思路还能用在哪题目11. 盛最多水的容器标签数组 · 双指针 · 贪心题目描述给定一个长度为n的非负整数数组height。在横坐标i处画一条高度为height[i]的竖线相邻位置的距离为1。选择两条竖线与横轴组成一个不能倾斜的容器。返回它能盛的最大水量也就是这个二维模型中的最大面积。每次只选两条线当边界中间的线不参与这次水量计算。输入height [1,8,6,2,5,4,8,3,7] 输出49选下标1和8的两条线高度分别是8、7间距为7因此面积是7 × 7 49。另一个例子height [1,1]只能选这两条线答案为1。数据范围2 n 10^50 height[i] 10^4。先看清高度和宽度都重要容器中的水会从较短的那一边溢出。所以选定下标left、right后宽度 right - left 水的高度 min(height[left], height[right]) 面积 宽度 × 水的高度不能只找最高的两条线。上面的数组中两个8位于下标1、6面积只有5 × 8 40小于49。把所有两条线的组合都试一遍当然可以但需要O(n²)时间。我们能否每看一对就排除一些不可能更好的组合为什么可以丢弃较短的那条边先把两个指针放在最左端和最右端此时宽度最大。假设左边较短或者两边一样高即height[left] height[right]。当前面积为(right - left) × height[left]如果保留这条左边界把右边界换成中间任意一条线宽度会变小。水的高度最多仍是height[left]还可能更低。因此在当前范围里保留这条左边界的其他组合都不会比刚算过的这一对更好。当前面积已经记下就可以放心排除left让它右移一步。右边较短时同理让right左移。两边等高时移动任意一边都成立下面的代码固定移动左边。整个过程就是先记录当前面积再移动较短的一边直到两个指针相遇。每次排除的组合都不可能超过已记录的面积因此不会漏掉最优答案。注意移动短边只是有机会遇到更高的边不保证下一次面积变大。所以还需要一个变量answer保存此前见过的最大面积。跟着例子走一遍仍然看height [1,8,6,2,5,4,8,3,7]第一步left 0、right 8水高为1面积为8。左边较短移动left。第二步left 1、right 8宽度虽然从8减到7水高却从1升到7面积变成49。这次右边较短接下来移动right。完整过程如下左右位置都使用从0开始的下标left, right较短边高度本次面积已知最大值0, 818 × 1 881, 877 × 7 49491, 736 × 3 18491, 685 × 8 40492, 664 × 6 24493, 623 × 2 6494, 652 × 5 10495, 641 × 4 449最后两个指针相遇返回49。从第二步到第三步面积就从49降到了18也能看出为什么要一直保留最大值。代码里的变量表示什么变量或表达式含义height[i]下标i处竖线的高度数组顺序就是竖线的位置顺序left、right本次选择的左右边界下标初始为0、n - 1right - left两条边界之间的距离也就是容器宽度shorter两侧高度中的较小值决定本次水位area当前这两条边界能围出的面积answer到目前为止找到的最大面积初始为0heightSizeC 版本中数组的元素个数对应题目中的n例如第二步shorter min(8, 7) 7area (8 - 1) × 7 49再用它更新answer。C 实现#includealgorithm#includevectorclassSolution{public:intmaxArea(conststd::vectorintheight){intleft0;intrightstatic_castint(height.size())-1;intanswer0;while(leftright){intshorterstd::min(height[left],height[right]);intarea(right-left)*shorter;answerstd::max(answer,area);// 保留短边再缩小宽度不可能得到更大的面积。if(height[left]height[right]){left;}else{--right;}}returnanswer;}};C main调用#includecerrno#includecstdlib#includeiostream#includesolution.cppstructTestCase{constchar*name;std::vectorintheight;intexpected;};staticboolrunCase(constTestCasetest,intnumber){Solution solution;intactualsolution.maxArea(test.height);boolpassedactualtest.expected;std::coutCase number (test.name)\n height [;for(std::size_t i0;itest.height.size();i){if(i!0)std::cout,;std::couttest.height[i];}std::cout]\n expected test.expected, actual actual - (passed?PASS:FAIL)\n;returnpassed;}intmain(intargc,char*argv[]){// 在这里修改输入及预期最大面积用例编号从 1 开始。conststd::vectorTestCasetests{{Example 1,{1,8,6,2,5,4,8,3,7},49},{Example 2,{1,1},1},{Zero heights,{0,0},0},{Increasing heights,{1,2,3,4,5},6},{Decreasing heights,{5,4,3,2,1},6},{Equal heights,{3,3,3,3},9},{Equal endpoints,{1,2,1},2},{Tallest pair is not optimal,{1,2,4,3},4},{Zero boundaries and middle,{0,2,0,2,0},4}};intcountstatic_castint(tests.size());intfirst0;intlastcount;if(argc2){std::cerrUsage: argv[0] [case-number: 1..count]\n;returnEXIT_FAILURE;}if(argc2){char*endnullptr;errno0;longnumberstd::strtol(argv[1],end,10);if(argv[1][0]0||argv[1][0]9||errnoERANGE||endargv[1]||*end!\0||number1||numbercount){std::cerrInvalid case number; choose 1..count.\n;returnEXIT_FAILURE;}firststatic_castint(number)-1;lastfirst1;}intpassed0;for(intifirst;ilast;i){if(runCase(tests[i],i1))passed;}intexecutedlast-first;std::coutSummary: passed/executed passed.\n;returnpassedexecuted?EXIT_SUCCESS:EXIT_FAILURE;}C 实现intmaxArea(int*height,intheightSize){intleft0;intrightheightSize-1;intanswer0;while(leftright){intshorterheight[left]height[right]?height[left]:height[right];intarea(right-left)*shorter;if(areaanswer){answerarea;}// 保留短边再缩小宽度不可能得到更大的面积。if(height[left]height[right]){left;}else{--right;}}returnanswer;}C main调用#includeerrno.h#includestdbool.h#includestdio.h#includestdlib.h#includestring.h#includesolution.ctypedefstruct{constchar*name;constint*height;intheightSize;intexpected;}TestCase;staticboolrunCase(constTestCase*test,intnumber){printf(Case %d (%s)\n height [,number,test-name);for(inti0;itest-heightSize;i){if(i!0)printf(,);printf(%d,test-height[i]);}printf(]\n);size_tbytes(size_t)test-heightSize*sizeof(int);int*heightmalloc(bytes);if(heightNULL){printf( expected %d, actual allocation failed - FAIL\n,test-expected);returnfalse;}memcpy(height,test-height,bytes);intactualmaxArea(height,test-heightSize);bool unchangedmemcmp(height,test-height,bytes)0;bool passedactualtest-expectedunchanged;printf( expected %d, actual %d, input unchanged %s - %s\n,test-expected,actual,unchanged?true:false,passed?PASS:FAIL);free(height);returnpassed;}intmain(intargc,char*argv[]){// 在这里修改输入及预期最大面积修改数组后同步调整 heightSize。constTestCase tests[]{{Example 1,(constint[]){1,8,6,2,5,4,8,3,7},9,49},{Example 2,(constint[]){1,1},2,1},{Zero heights,(constint[]){0,0},2,0},{Increasing heights,(constint[]){1,2,3,4,5},5,6},{Decreasing heights,(constint[]){5,4,3,2,1},5,6},{Equal heights,(constint[]){3,3,3,3},4,9},{Equal endpoints,(constint[]){1,2,1},3,2},{Tallest pair is not optimal,(constint[]){1,2,4,3},4,4},{Zero boundaries and middle,(constint[]){0,2,0,2,0},5,4}};intcount(int)(sizeof(tests)/sizeof(tests[0]));intfirst0;intlastcount;if(argc2){fprintf(stderr,Usage: %s [case-number: 1..%d]\n,argv[0],count);returnEXIT_FAILURE;}if(argc2){char*endNULL;errno0;longnumberstrtol(argv[1],end,10);if(argv[1][0]0||argv[1][0]9||errnoERANGE||endargv[1]||*end!\0||number1||numbercount){fprintf(stderr,Invalid case number; choose 1..%d.\n,count);returnEXIT_FAILURE;}first(int)number-1;lastfirst1;}intpassed0;for(intifirst;ilast;i){if(runCase(tests[i],i1))passed;}intexecutedlast-first;printf(Summary: %d/%d passed.\n,passed,executed);returnpassedexecuted?EXIT_SUCCESS:EXIT_FAILURE;}复杂度与易错点设数组长度为n。每轮让两个指针的距离减少1一共计算n - 1对边界因此时间复杂度为O(n)额外空间为O(1)。宽度是right - left不加1。下标0和1的距离是1。先算面积、更新答案再移动指针。循环条件是left right需要两条不同的边界。不要排序。排序会改变竖线的原始位置间距也就变了。高度为0也正常处理。面积可能一直是0所以答案从0开始。在本题范围内面积最多为99999 × 10000 999990000使用 32 位int足够如果扩大范围需要相应使用更宽的整数类型。这套思路还能用在哪可以设计一个二维容器布局小工具给出若干候选挡板的位置和高度选择两块让围出的面积最大。如果位置间距不再相同只要横坐标x[i]已从小到大排列就把宽度改成x[right] - x[left]仍然可以移动短边。这个推广依赖相同的条件高度非负、水位由两端较低者决定内部挡板不额外限制水位。遇到类似的配对优化问题可以先检查固定某一端以后其他组合是否都不可能更好从而整批排除。也可以接着看 1658. 将 x 减到 0 的最小操作数它同样移动两个边界但依据的是正数区间和的变化这题依据的是宽度与短边的限制移动规则各有原因。