企业官网建设流程全解析

题目：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^5，0 <= 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开始的下标：

最后两个指针相遇，返回49。从第二步到第三步，面积就从49降到了18，也能看出为什么要一直保留最大值。

代码里的变量表示什么？

例如第二步，shorter = min(8, 7) = 7，area = (8 - 1) × 7 = 49，再用它更新answer。

C++ 实现

#include<algorithm>#include<vector>classSolution{public:intmaxArea(conststd::vector<int>&height){intleft=0;intright=static_cast<int>(height.size())-1;intanswer=0;while(left<right){intshorter=std::min(height[left],height[right]);intarea=(right-left)*shorter;answer=std::max(answer,area);// 保留短边再缩小宽度，不可能得到更大的面积。if(height[left]<=height[right]){++left;}else{--right;}}returnanswer;}};

C++ main调用

#include<cerrno>#include<cstdlib>#include<iostream>#include"solution.cpp"structTestCase{constchar*name;std::vector<int>height;intexpected;};staticboolrunCase(constTestCase&test,intnumber){Solution solution;intactual=solution.maxArea(test.height);boolpassed=actual==test.expected;std::cout<<"Case "<<number<<" ("<<test.name<<")\n height = [";for(std::size_t i=0;i<test.height.size();++i){if(i!=0)std::cout<<',';std::cout<<test.height[i];}std::cout<<"]\n expected = "<<test.expected<<", actual = "<<actual<<" -> "<<(passed?"PASS":"FAIL")<<"\n";returnpassed;}intmain(intargc,char*argv[]){// 在这里修改输入及预期最大面积；用例编号从 1 开始。conststd::vector<TestCase>tests={{"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}};intcount=static_cast<int>(tests.size());intfirst=0;intlast=count;if(argc>2){std::cerr<<"Usage: "<<argv[0]<<" [case-number: 1.."<<count<<"]\n";returnEXIT_FAILURE;}if(argc==2){char*end=nullptr;errno=0;longnumber=std::strtol(argv[1],&end,10);if(argv[1][0]<'0'||argv[1][0]>'9'||errno==ERANGE||end==argv[1]||*end!='\0'||number<1||number>count){std::cerr<<"Invalid case number; choose 1.."<<count<<".\n";returnEXIT_FAILURE;}first=static_cast<int>(number)-1;last=first+1;}intpassed=0;for(inti=first;i<last;++i){if(runCase(tests[i],i+1))++passed;}intexecuted=last-first;std::cout<<"Summary: "<<passed<<'/'<<executed<<" passed.\n";returnpassed==executed?EXIT_SUCCESS:EXIT_FAILURE;}

C 实现

intmaxArea(int*height,intheightSize){intleft=0;intright=heightSize-1;intanswer=0;while(left<right){intshorter=height[left]<height[right]?height[left]:height[right];intarea=(right-left)*shorter;if(area>answer){answer=area;}// 保留短边再缩小宽度，不可能得到更大的面积。if(height[left]<=height[right]){++left;}else{--right;}}returnanswer;}

C main调用

#include<errno.h>#include<stdbool.h>#include<stdio.h>#include<stdlib.h>#include<string.h>#include"solution.c"typedefstruct{constchar*name;constint*height;intheightSize;intexpected;}TestCase;staticboolrunCase(constTestCase*test,intnumber){printf("Case %d (%s)\n height = [",number,test->name);for(inti=0;i<test->heightSize;++i){if(i!=0)printf(",");printf("%d",test->height[i]);}printf("]\n");size_tbytes=(size_t)test->heightSize*sizeof(int);int*height=malloc(bytes);if(height==NULL){printf(" expected = %d, actual = allocation failed -> FAIL\n",test->expected);returnfalse;}memcpy(height,test->height,bytes);intactual=maxArea(height,test->heightSize);bool unchanged=memcmp(height,test->height,bytes)==0;bool passed=actual==test->expected&&unchanged;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]));intfirst=0;intlast=count;if(argc>2){fprintf(stderr,"Usage: %s [case-number: 1..%d]\n",argv[0],count);returnEXIT_FAILURE;}if(argc==2){char*end=NULL;errno=0;longnumber=strtol(argv[1],&end,10);if(argv[1][0]<'0'||argv[1][0]>'9'||errno==ERANGE||end==argv[1]||*end!='\0'||number<1||number>count){fprintf(stderr,"Invalid case number; choose 1..%d.\n",count);returnEXIT_FAILURE;}first=(int)number-1;last=first+1;}intpassed=0;for(inti=first;i<last;++i){if(runCase(&tests[i],i+1))++passed;}intexecuted=last-first;printf("Summary: %d/%d passed.\n",passed,executed);returnpassed==executed?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 的最小操作数：它同样移动两个边界，但依据的是正数区间和的变化；这题依据的是宽度与短边的限制，移动规则各有原因。