C++ 编程练习题 – 最多水容器 (递归)
题意: 给定一个数组, 每个数值代表柱子的高度, 那么求出这些柱子最多可以装多少水. 水的体积由较短的长度乘以两个柱子的距离. 上面的图的输入为 . 蓝色区域最可以装水为49. 最简单的方法就是暴力穷举, 那么复杂度为 O(n^2) , 需要穷举n*(n-1)/2对高度. 可以用递归来实现, 但是递归需要额外O(n) 的空间 – 调用堆栈: class Solution { public: int f(vector<int>& height, int j) { if …
