首页 > 其他分享 > 42 接雨水

42 接雨水

时间:2022-11-16 12:44:07浏览次数:36  
标签:right int max 42 雨水 height 高度 left

算法1.三次线性扫描\(O(n)\)

  1. 观察整个图形,考虑对水的面积按 列 进行拆解

  2. 注意到,每个矩形条上方所能接受的水的高度,是由它左边 最高的 矩形,和右边最高的矩形决定的。

  3. 具体地,假设第 i 个矩形条的高度为 height[i],且矩形条左边 最高的 矩形条的高度为 left_max[i],右边 最高的 矩形条高度为 right_max[i],则该矩形条上方能接受水的高度为 min(left_max[i], right_max[i]) - height[i]

  4. 分别从左向右扫描求 left_max,从右向左求 right_max,最后统计答案即可。

    注意特判 n 为 0。

时间复杂度

三次线性扫描,故只需要 O(n) 的时间。

空间复杂度

需要额外 O(n) 的空间记录每个位置左边最高的高度和右边最高的高度。

代码

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        vector<int> left_max(n), right_max(n);
        left_max[0] = height[0];
        for(int i = 1; i < n; i++)
            left_max[i] = max(left_max[i - 1], height[i]);

        right_max[n - 1] = height[n - 1];
        for(int i = n - 2; i >= 0; i--)
            right_max[i] = max(right_max[i + 1], height[i]);

        int ans = 0;
        for(int i = 0; i < n; i++)
            ans += min(left_max[i], right_max[i]) - height[i];
        return ans;
    }
};

算法2.单调栈

换一种思路,按行进行拆分

image-20221116122345635
  1. 维护一个递减的单调栈
  2. 0 1 2都是递减的,即当前高度小于栈顶高度,所以入栈
  3. 当走到3时,3的高度比栈顶2的高度要高,所以要出栈计算
    1. 先将单调栈的栈顶2的弹出,然后加上1、2和3构成的水沟的高度
    2. 再将单调栈的栈顶1的弹出,加上0123构成的水沟高度
    3. 不断重复,直到栈顶高度高于3的高度,将3入栈

代码

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size(), ans = 0, top = -1;
        int stack[n];

        for(int i = 0; i < n; i++)
        {
            while(top != -1 && height[stack[top]] <= height[i])
            {
                int buttom = stack[top--];
                if(top == -1) break;
                int l = stack[top];
                ans += (min(height[i], height[l]) - height[buttom]) * (i - l - 1);
            }
            stack[++top] = i;
        }
        return ans;
    }
};

标签:right,int,max,42,雨水,height,高度,left
From: https://www.cnblogs.com/INnoVationv2/p/16895500.html

相关文章

  • 1742C
    题目链接题目大意:在一个8x8的方格中你每次可以将一行全部涂成红色或者将一列涂成蓝色。问最后一次操作是什么操作:如果是行操作就输出R如果是列操作就输出B解题思路:......
  • LibreOJ #6042. 「雅礼集训 2017 Day7」跳蚤王国的宰相
    题意修改一条边意味着,删掉一条边,并加入一条新的边。给出一棵树,对于每个点,求出使它变成重心的最小修改边数。分析先找到重心,对于不是重心的一个点\(i\),有两种方法,一是......
  • 42、使用mmrotate中k3det进行旋转目标检测,并进行mnn部署和ncnn部署
    基本思想:仍然是身份证分割,因为上一个篇博客的效果不好,所以操刀改mm系列的框架,并进行ncnn和mnn的c++的部署开发mmcv_full1.6.1+mmrotatev0.3.2测试没有问题mmcv_full1.4.6+mm......
  • 洛谷 P6142
    先对\(k\)进行二分,将最值问题转化成判定问题。判定一个\(k\)是否合法时,贪心去考虑,一个节点下面的若干条链在合并时,一条链肯定和另一条使它合并后恰好满足长度限制的链......
  • 2022-2023-1 20221420《计算机基础与程序设计》第十一周学习总结
    作业信息这个作业属于哪个课程:这个作业的要求在:2022-2023-1《计算机基础与程序设计》教学进程-娄老师-博客园(cnblogs.com)这个作业的目标:自主学习《C语言程序设......
  • 20221427第十一周学习总结
    20221427第十一周学习总结这个作业属于哪个课程 这个作业要求在哪里<作业要求的链接>https://www.cnblogs.com/rocedu/p/9577842.html#WEEK11这个作业的目标<......
  • AT32F421xx外设驱动4-uart(寄存器)
    #include"BspPhy.h"//****************************************************************//******串口GPIO初始化函数//******输入参数:无//******返回值:......
  • AT32F421xx外设驱动3-timer(寄存器)
    #include"BspPhy.h"uint8_tTimerFlag;//****************************************************************//******定时器6初始化函数//******输入参数:无......
  • AT32F421xx外设驱动2-delay(寄存器)
    #include"BspPhy.h"staticuint32_tfac_us;staticuint32_tfac_ms;voidPhyDelayInit(){SysTick->CTRL|=SYSTICK_CLOCK_SOURCE_AHBCLK_NODIV;fac_us=s......
  • AT32F421xx外设驱动1-led(寄存器)
    //****************************************************************//******连接LED指示灯GPIO初始化函数PA4//******输入参数:无//******返回值:无/......