前言

本专栏文章为《LeetCode 热题 100》的刷题题解，相关内容如有侵权，立即删除。

一、题目

1、原题链接

11.盛最多水的容器

2、题目描述

二、个人思路整理

1、思路分析

• 核心思路是对向双指针（贪心策略）。
• 容器容纳的水量公式为：$$\text{Area}=(r-l)\times \min (height[l],height[r])$$
• 移动策略：每次比较左右两边，固定较长的一边，向内移动较短的那一边。

• 为什么不能移动长边？
  如果移动长边，底边宽度 $r-l$ 必定减小，而容器的高度受限于原来的短边，最多只能维持原短边的高度甚至更低。因此，面积必定严格减小。移动长边不可能产生更优解。
• 为什么移动短边才可能更优？
  虽然宽度变小，但如果移动后的新柱子比原短边更高，容器的有效高度可能会提升，从而有机会获得更大的面积。

• 终止条件：当两指针相遇（l==r）时遍历结束，期间记录的最大面积即为全局最优解

复杂度分析

• 时间复杂度：$O(n)$，双指针各向中间移动一次，整体遍历一遍数组。
• 空间复杂度：$O(1)$，仅使用常数级额外空间。

2、解题代码

class Solution {
public:
    int maxArea(vector<int>& height) {
        // 初始化双指针：left指向数组首端，right指向数组尾端
        // 初始化下底边宽度(right - left)最大
        int left = 0, right = height.size() - 1;
        
        // 记录遍历过程中出现的最大盛水量
        int max_water = 0;
        
        // 当左右指针相遇时循环终止
        while(left < right) {
            // 容器的容水量公式：底边宽度 * 两端较矮柱子的高度（木桶效应）
            int current_water = (right - left) * min(height[left], height[right]);
            
            // 更新全局最大容水量
            max_water = max(max_water, current_water);
            
            // 贪心策略：移动较矮的那一侧指针
            // 原因：
            // 1. 若移动较长边，底边宽度变小，而容器高度受限于原短边（不可能超过短边），面积必定减下。
            // 2. 若移动较短边，虽然宽度减小，但新柱子有可能更高，从而带来面积增大的可能。
            if(height[left] < height[right]) {
                left++;  // 左侧较矮，左指针右移寻找更高的柱子
            }
            else {
                right--;  // 右侧较矮（或两者等高），右指针左移寻找更高的柱子
            }
        }
        return max_water;
    }
};

三、知识风暴

1. 对向双指针（Two Pointers）

• 本质：利用单调性排除无效状态，将 $O(n^2)$ 暴力穷举优化至 $O(n)$。
• 适用：区间边界最值（面积/容量）、有序数组查找（两数之和）。

2. 贪心突破短板

• 短板效应：$\text{Area}=(r-l)\times \min (h_l,h_r)$，面积由较矮边决定。
• 移动策略：宽度必然减小，移动长边必变小，移动短边才可能变大。