LeetCode 11. 盛最多水的容器

    科技2025-05-07  59

    算法流程: 1.两个指针分别位于初始位置和结束位置 2.指针值偏小的一方往里走,同时计算面积最大值 为什么要指针值偏小的往里走? 假设左侧指针先到达最优位置(右侧同理,证明略)。如果右侧指针比左侧大,右侧指针不应该移动。理由是,假设存在右侧最优面积,右侧最优值(右边第二个线)无论是比左侧最优值高还是低,构成的面积均小于最右侧指针构成的面积。所以出现矛盾。而右侧指针比左侧小的话,就要往里走,计算比较一下可能的面积大小。

    class Solution { public: int maxArea(vector<int>& height) { int res = 0; for(int i = 0, j = height.size() - 1; i < j;){ res = max(res, (j - i) * min(height[i], height[j])); if(height[i] > height[j]) j --; else i ++; } return res; } };
    Processed: 0.011, SQL: 8