11. Container With Most Water 最多存水量

    xiaoxiao2023-11-08  178

    求最多能够存水量,(长*高) Example: Input: [1,8,6,2,5,4,8,3,7] Output: 49

    思考: 这道题有两种解法,方法1,暴力求解,时间复杂度O(n^2),计算出每个可能的面积取最大值。方法2,两个指针,一个left,一个right指针,计算面积, 每次比较这两个指针,低的一边移动指针,这种方法只需要遍历一遍数组。不过不太好想到。

    解法:(方法2)

    int maxArea(vector<int>& height) { int low = 0; int high = height.size() - 1; int area_max = 0; while (low < high) { area_max = max(area_max, min(height[low], height[high]) * (high - low)); if (height[low] < height[high]) { ++low; } else { --high; } } return area_max; }

     

    最新回复(0)