题目大意:平面上有若干与y轴平行的线段,这些线段的一个端点一定在x轴上,另一个端点一定在第一象限。对于任意两条线段,其都与x轴一起形成一个“容器”,“容器”可以用来装水,水的高度等于较短侧边的高度。现在问所有“容器”中容量最大的是多少。

关键字:最优化剪枝

题目描述

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.

解法1:朴素

最简单的朴素方法便是枚举容器的两条边,即所有的O(n^2)种可能,然后在这其中找到最优的一组边为最优解。

解法2:最优化剪枝

考虑改变枚举容器的顺序,首先看编号为0和n-1的两条边组成的容器,令其为当前最优解。

不妨设height[0] < height[n-1],那么所有左边界为0的容器一定都比当前最优解要差(水的高度相同但是宽度变小),于是可以忽略这样的方案。

所以问题规模缩小了1(变为在编号为1..n-1的边中找两条边来组成容器),依次类推,每次将问题的规模缩小1,最后只需要统计O(n)个容器的最优解即可。

class Solution {
public:
    int maxArea(vector<int>& height) {
        // 全局最优解和初始问题
        int ans = 0, l = 0, r = height.size() - 1;
        // 当前问题规模不为1时继续进行
        while (l < r) {
            // 以最左侧的边和最右侧的边构成的容器来更新答案
            ans = max(ans, (r - l) * min(height[l], height[r]));
            // 根据两侧边的高度,来“剪枝”掉那些必然不会构成最优解的方案
            if (height[l] < height[r]) {
                l ++;
            }
            else {
                r --;
            }
        }
        // 返回答案
        return ans;
    }
};

登录发表评论 注册

反馈意见