C++ 编程练习题 – 最多水容器 (递归)

JustYY.com 小赖子的英国生活和资讯

6 years ago

题意: 给定一个数组, 每个数值代表柱子的高度, 那么求出这些柱子最多可以装多少水. 水的体积由较短的长度乘以两个柱子的距离.

编程练习题 – 最多水容器 (递归)

上面的图的输入为 [1,8,6,2,5,4,8,3,7]. 蓝色区域最可以装水为49.

最简单的方法就是暴力穷举, 那么复杂度为 O(n^2) , 需要穷举n*(n-1)/2对高度. 可以用递归来实现, 但是递归需要额外O(n) 的空间 – 调用堆栈:

class Solution {
public:
    int f(vector<int>& height, int j) {
        if (j == 0) return 0;
        if (j == 1) return min(height[0], height[1]);
        int r = f(height, j - 1);
        for (int k = 0; k < j; k ++) {
            r = max(min(height[k], height[j]) * (j - k), r);
        }        
        return r;
    }
    
    int maxArea(vector<int>& height) {        
        return f(height, height.size() - 1);
    }
};

class Solution {
public:
    int f(vector<int>& height, int j) {
        if (j == 0) return 0;
        if (j == 1) return min(height[0], height[1]);
        int r = f(height, j - 1);
        for (int k = 0; k < j; k ++) {
            r = max(min(height[k], height[j]) * (j - k), r);
        }        
        return r;
    }
    
    int maxArea(vector<int>& height) {        
        return f(height, height.size() - 1);
    }
};

我们这里定义了一个 f(j) 表示从0号柱子到 j 号柱子的最大装水量. 那么两种情况, 要么 j 号柱子是最终最右边的那个柱子(这时候需要穷举左边柱子从0到 j-1 号), 要么不是 f(j-1).

时间复杂度为O(n^2), 空间复杂度为 O(n) – 调用堆栈. 实际上, 我们可以较简单的用 O(n^2) 来穷举每一对, 代码显得更简单, 并且空间复杂度也只需要常数级 O(1).

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

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

实际上, 最优解是 O(n), 我们最先在两端建立一个容易, 两个指针, 同时记录当前最大装水量, 每次移动最短边逐渐往中间移动. 为什么呢? 因为如果你移动最长边的那端, 装水量肯定不会增加, 因为装水量是由最短边确定的. 移动最短边有可能获得更大的装水量(来弥补X轴距离的缩短). 这也就是贪心算法.

class Solution {
public:   
    int maxArea(vector<int>& height) {        
        int maxarea = 0, l = 0, r = height.size() - 1;
        while (l < r) {
            maxarea = max(maxarea, min(height[l], height[r]) * (r - l));
            if (height[l] < height[r])
                l++;
            else
                r--;
        }
        return maxarea;
    }
};

class Solution {
public:   
    int maxArea(vector<int>& height) {        
        int maxarea = 0, l = 0, r = height.size() - 1;
        while (l < r) {
            maxarea = max(maxarea, min(height[l], height[r]) * (r - l));
            if (height[l] < height[r])
                l++;
            else
                r--;
        }
        return maxarea;
    }
};

前两种都是O(n^2) 的算法, 大概通过50个测试点需要费时1秒钟, 而最后一种 O(n) 算法只需要12毫秒.

英文: Coding Exercise – Container With Most Water (Recursion)

强烈推荐

英国代购-畅购英伦
TopCashBack 返现 (英国购物必备, 积少成多, 我2年来一共得了3000多英镑)
Quidco 返现 (也是很不错的英国返现网站, 返现率高)
注册就送10美元, 免费使用2个月的 DigitalOcean 云主机(性价比超高, 每月只需5美元)
注册就送10美元, 免费使用4个月的 Vultr 云主机(性价比超高, 每月只需2.5美元)
注册就送10美元, 免费使用2个月的阿里云主机(性价比超高, 每月只需4.5美元)
注册就送20美元, 免费使用4个月的 Linode 云主机(性价比超高, 每月只需5美元) (折扣码: PodCastInit2022)
PlusNet 英国光纤(超快, 超划算! 用户名 doctorlai)
刷了美国运通信用卡一年得到的积分换了 485英镑
注册就送50英镑 – 英国最便宜最划算的电气提供商
能把比特币莱特币变现的银行卡! 不需要手续费就可以把虚拟货币法币兑换

微信公众号: 小赖子的英国生活和资讯 JustYYUK

阅读 桌面完整版

强烈推荐

相关文章：