当前位置：网站首页>363 · 接雨水

363 · 接雨水

2022-04-22 06:15:00 【yinhua405】

描述

给出 n 个非负整数，代表一张X轴上每个区域宽度为 1 的海拔图, 计算这个海拔图最多能接住多少（面积）雨水。

微信加 jiuzhang15 发送验证信息【国内大厂】领字节、阿里、百度等最新高频题

样例

样例 1:

 
 
输入: [0,1,0]
输出: 0
 
 
样例 2:
 
 
 
 
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
 
 
挑战
 
 
O(n) 时间, O(1) 空间
 
 
O(n) 时间, O(n) 空间也可以接受
 
 
 
 

 int trapRainWater(vector<int> &heights)
 {
  
 
 
    if (heights.size() < 2)
     {
  
         return 0;
     }
     int sum = 0;
     int leftCurMax = 0;
     vector<int> rightMaxVec(heights.size(),-1);
     int left = 0;
     leftCurMax = max(leftCurMax, heights[left]);
     int rightMax = 0;
     for (int right = heights.size() - 1; right >= 2;  right--)
     {
  
         rightMaxVec[right] = max(rightMax, heights[right]);
         rightMax = rightMaxVec[right];
     }
     sum += max(0, min(leftCurMax, rightMax) - heights[1]);
     
 
 
    for (int index = 2; index < heights.size()-1; index++)
     {
  
         leftCurMax = max(leftCurMax, heights[index-1]);
         int rightMax = rightMaxVec[index+1];    
         sum += max(0,min(leftCurMax, rightMax) - heights[index]);
     }
     return sum;
 }
 


                

                    
版权声明 

                        本文为[yinhua405]所创，转载请带上原文链接，感谢

                        https://blog.csdn.net/yinhua405/article/details/123470194
                    

                

            


            
            



            


        

        

        

    

    

        



        


边栏推荐





        


猜你喜欢

        



        


随机推荐