题目链接:https://leetcode.cn/problems/container-with-most-water/
这道题,也是只能想到最笨的方法,两层循环,复杂度最高,所以提交之后就提示运行超时。。。。
等我研究官方题解再来更新吧。。。
已更新,官方的双指针法,关键是移动左右两边哪个X轴坐标,这里选的是Y轴低的,这样才有可能补偿X轴(也就是底边)减少1导致的面积缩小问题:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
class Solution { public: /* 暴力搜索法 int maxArea(vector<int>& height) { int area = 0; for (int i = 0; i < height.size(); i++) { for (int j = i + 1; j < height.size(); j++) { int newarea = (j - i) * min(height[i], height[j]); area = max(area, newarea); } } return area; } */ int maxArea(vector<int>& height) { int area = 0; int i = 0, j = height.size() - 1; while (i < j) { area = max(area, (j - i) * min(height[i], height[j])); if (height[i] < height[j]) { i++; } else { j--; } } return area; } }; |