• leetcode


    给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。

    示例 1:

    输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]
    输出:6
    解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。 


    示例 2:

    输入:height = [4,2,0,3,2,5]
    输出:9
     

    提示:

    n == height.length
    1 <= n <= 2 * 104
    0 <= height[i] <= 105

     思路一:

    感觉这个题好像在哪做过,当时就是使用暴力,所以我又写了一下;

    首先是先找到最高的柱子,然后依次找到最左边的柱子和最右边的柱子,再找到最低的柱子;

    然后将最左边到最右边的所有柱子都减去最短柱子的长度,若不是柱子,则将海水的数量加上最低的柱子高度,相当于把 X 轴向上移动最低柱子的高度。

    1. int trap(int* height, int heightSize){
    2. int ans = 0, height_max= height[0];
    3. //找到最高的数字
    4. for(int i = 1; i < heightSize; i++)
    5. height_max = height_max > height[i] ? height_max : height[i];
    6. int left = 0, right = heightSize - 1, flag = 0;
    7. //从低到高依次处理每层能接多少水
    8. for(int i = 0; i < height_max; i++){
    9. left = flag;
    10. //找到最左边的柱子
    11. for(; left < heightSize; left++)
    12. if(height[left])
    13. break;
    14. flag = left;
    15. //找到最右边的柱子
    16. for(; right >= left; right--)
    17. if(height[right])
    18. break;
    19. int height_min = 1000020;
    20. //找到最低的柱子
    21. for(int j = left; j <= right; j++)
    22. if(height[j])
    23. height_min = height_min < height[j] ? height_min : height[j];
    24. //将最左的柱子和最右边的柱子之间水记录下来
    25. while(left <= right){
    26. if(height[left]) //若为柱子则将柱子的长度减去最低的柱子
    27. height[left] -= height_min;
    28. else //若不是柱子则将是水,将水的数量加最低的柱子
    29. ans += height_min;
    30. left++;
    31. }
    32. }
    33. return ans;
    34. }

     思路二:

    找到最高柱子的下标,以最高的柱子将图分为左右两部分,然后对两边的图分别处理;

    先处理左边柱子能存多少海水,找到i柱子右边第一个比i高的柱子j,则它们之间一定都比i柱子低,因此只需要用i柱子的高度减去i-j之间柱子的高度就是能接的海水,然后找 j 柱子右边第一个比 j 高的柱子,依次循环,右边的同理。

    1. int trap(int* height, int heightSize){
    2. if(heightSize == 1)
    3. return 0;
    4. int height_max = 0, height_max_i = 0;
    5. //找到最高的柱子,和柱子的下表
    6. for(int i = 0; i < heightSize; i++){
    7. if(height_max < height[i]){
    8. height_max_i = i;
    9. height_max = height[i];
    10. }
    11. }
    12. int ans = 0;
    13. //处理最高柱子左边能接多少海水
    14. //找到i柱子右边第一个比i高的柱子j,则它们之间一定都比i柱子低,因此只需要用i柱子的高度减去i-j之间柱子的高度就是能接的海水
    15. for(int i = 0; i < height_max_i;){
    16. int j = i + 1;
    17. for(; j <= height_max_i; j++) //找到右边第一个比i高的柱子
    18. if(height[i] < height[j])
    19. break;
    20. for(int k = i + 1; k < j; k++) //求出i-j之间海水的数量
    21. ans += height[i] - height[k];
    22. i = j;
    23. }
    24. //处理最高柱子右边能接多少海水
    25. //找到i柱子左边第一个比i高的柱子j,则它们之间一定都比i柱子低,因此只需要用i柱子的高度减去j-i之间柱子的高度就是能接的海水
    26. for(int i = heightSize - 1; i > height_max_i;){
    27. int j = i - 1;
    28. for( ; j >= height_max_i; j--)//找到右边第一个比i高的柱子
    29. if(height[i] < height[j])
    30. break;
    31. for(int k = i - 1; k > j; k--) //求出j-i之间海水的数量
    32. ans += height[i] - height[k];
    33. i = j;
    34. }
    35. return ans;
    36. }

  • 相关阅读:
    spring-data-mongodb生成的Query语句order字段顺序错误
    使用OpenCVSharp利用PictrueBox对接摄像头获取视频图像
    Cpp(Python)和MATLAB差动驱动ROS Raspberry Pi全功能机器人原型
    【JavaSE】类与对象(上)类是什么?对象是什么?
    「尚硅谷与腾讯云官方合作」硅谷课堂项目视频发布
    一个月速刷leetcodeHOT100 day13 二叉树结构 以及相关简单题
    Python将字符串转换成dataframe
    SpringBoot快速部署(2)—不使用docker的常规方法
    千万级别的表分页查询非常慢,怎么办?
    极智嘉(Geek+)柔性货箱到人拣选方案,助力Starlinks实现高效运营
  • 原文地址:https://blog.csdn.net/qq_41555003/article/details/126480678