当前位置: 代码迷 >> 综合 >> leetcode 42. Trapping Rain Water (hard)
  详细解决方案

leetcode 42. Trapping Rain Water (hard)

热度:61   发布时间:2024-01-05 00:32:02.0

找出最高的柱子,分别计算其两边的柱子
对左边的每个点而言

其左边最大柱子的高度 - 其本身的高度 = 这一点能容纳的水量

右边同理

class Solution
{
    public:int trap(vector<int> &height){
    int partionPeak = 0;int sumWater = 0;// 分界点for (int i = 0; i < height.size(); i++)if (height[i] > height[partionPeak])partionPeak = i;int leftPeak = 0;for (int i = 0; i < partionPeak; i++){
    if (height[i] > leftPeak)leftPeak = height[i];elsesumWater += leftPeak - height[i];}int rightPeak = 0;for (int i = height.size() - 1; i > partionPeak; i--){
    if (height[i] > rightPeak)rightPeak = height[i];elsesumWater += rightPeak - height[i];}return sumWater;}
};