Leetcode 11. 收集最多的雨水 Container With Most Water

xiaoxiao2022-07-05  5


某平台价值19860元的编程课程资料免费领取【点我领取】


 解决方案:

利用双指针法进行雨水的计算,先用第一个和最后一个柱子开始收集雨水,这时两个柱子的距离是最远的。不断收缩两个柱子之间的距离,并来收集雨水,因为在收缩过程中,柱子之间的距离不断减小,要想收集更多的雨水,柱子必须要更高。因此在收缩过程中要跳过高度不满足的柱子,然后计算新的容器的收集雨水。

//收集最多的雨水 class Solution { public: int maxArea(vector<int>& height) { int i = 0, j = height.size() - 1; //i和j分别指向用来收集雨水的左右两个柱子 int water = 0; //保存雨水的量 while(i < j) //只要i不等于j,这两个柱子就能储存雨水 { int h = min(height[i], height[j]); //取两个柱子高度较小的那个 water = max(water, (j - i) * h); while(height[i] <= h && i < j) i++; //从两边交替进行收缩 while(height[j] <= h && i < j) j--; } return water; } };

 

 

转载请注明原文地址: https://www.6miu.com/read-4968470.html

最新回复(0)