LeetCode

Leetcode 11. Container With Most Water题解

查阅更多的题解,请点击

Problem

11. Container With Most Water

Solution

two pointer, O(n) time, O(1) space

按照解决问题的一般套路(参考算法笔记(一)概述):观察问题能不能reduce:输入数据为数组,按照常见的方式无法reduce;则考虑观察解空间,先给出一个解,再逐步优化到最优解。

最容易得到的一个结果是:数组第一个元素作为container的左边界,最后一个元素作为右边界,那么container的高为min(左边界,右边界)

  • 左边界的优化策略:只有当左边界大于上一个解的高时,有可能得到更好的解
  • 右边界的优化策略:只有当右边界大于上一个解的高时,有可能得到更好的解
  • 约束条件:左右边界相遇停止

GitHub传送门

class Solution
{
public:
    int maxArea(vector<int> &height)
    {
        int i = 0, j = height.size() - 1, water = 0;
        while (i < j)
        {
            int h = min(height[i], height[j]);
            water = max(water, (j - i) * h);
            while (height[i] <= h && i < j)
                i++;
            while (height[j] <= h && i < j)
                j--;
        }
        return water;
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注