题意: 给定一个数组, 每个数值代表柱子的高度, 那么求出这些柱子最多可以装多少水. 水的体积由较短的长度乘以两个柱子的距离.
上面的图的输入为 [1,8,6,2,5,4,8,3,7]. 蓝色区域最可以装水为49.
最简单的方法就是暴力穷举, 那么复杂度为 O(n^2) , 需要穷举n*(n-1)/2对高度. 可以用递归来实现, 但是递归需要额外O(n) 的空间 – 调用堆栈:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | 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).
1 2 3 4 5 6 7 8 9 10 11 12 | 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轴距离的缩短). 这也就是贪心算法.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | 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)
GD Star Rating
loading...
本文一共 421 个汉字, 你数一下对不对.loading...
上一篇: C编程练习题: 翻转整数位
下一篇: C++ 编程练习题 - 左子树叶节点之和 (深度优先+广度优先+递归)
扫描二维码,分享本文到微信朋友圈