LeetCode 11 - 盛最多水的容器

思路

容器面积由 宽度 和 短板高度 决定。最优解一定藏在不断收窄宽度的过程中。

1. 初始化：left 指针在数组头部，right 指针在尾部。这是最宽的可能。
2. 移动策略：比较 height[left] 和 height[right]。
   • 面积受限于短板。若移动长板，宽度变小，高度不变（或变小），面积必然减小。
   • 因此，必须移动短板对应的指针。这虽然牺牲了宽度，但给了我们寻找更高板子的机会，面积才有可能增大。
3. 迭代：循环此过程，持续更新最大面积，直到两指针相遇。

C++ 代码实现

classSolution{public:intmaxArea(vector<int>& height){int left =0;int right = height.size()-1;int maxArea =0;while(left < right){int currentArea =min(height[left], height[right])*(right - left); maxArea =max(maxArea, currentArea);if(height[left]< height[right]){ left++;}else{ right--;}}return maxArea;}};

复杂度

• 时间复杂度: O(n)，left 和 right 指针总共只会遍历数组一次。
• 空间复杂度: O(1)，仅使用常数个变量。