每日算法系列【LeetCode 42】接雨水

题目描述

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

image

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。感谢 Marcos 贡献此图。

示例1

输入:
[0,1,0,2,1,0,1,3,2,1,2,1]
输出:
6

题解

方法1(按列算)

这也是最容易理解的一种方法,我们计算每一个柱子上方的水最多有多高就行了,而这个高度取决于它的左右两边最高的柱子分别是多高。

当然可以暴力求左右两端最高的高度了,不过其实只需要预处理一下,用数组保存一下每个位置左右两端最高的高度就行了。

最后答案的话就是用左右两边最高高度的较小值,减去这根柱子的高度。

时间复杂度 O(n) ,空间复杂度 O(n) ,需要扫描两遍数组。

方法2(按行算)

我们可以发现,每一行水左右肯定都会被柱子卡住(显然是废话)。那么从左向右遍历柱子,如果高度在下降,那么显然不会蓄水。如果高度上升了,那就说明中间是个低点,这之间可以蓄水。而这个下降的高度用单调栈来维护就行了,栈里我们只放下标。

那到底蓄水多少呢?假设 q 是栈顶下标,p 是栈顶第二个元素下标,那么一定有 h[p] \ge h[q] 。现在进来一个 h[i] > h[q] ,那么 q 就是一个低点,而 p , q , i 之间的蓄水(比 h[q] 高,比 h[p]h[i] 都低的部分)可以计算为 (\min(h[p], h[i]) - h[q])\cdot(i - p - 1) 。然后把 q 出栈,继续用栈顶两个元素计算。

那么为什么这里只需要计算 p 和 i 之间比 h[q] 高的那部分矩形就行了呢?因为比它低的部分在之前都已经算过了,而比它高的部分在之后还会计算到。

用下面这张示意图可以看的更清楚一点:

image

红色表示栈里的元素,白色表示已经出栈了,绿色表示当前准备进栈的元素。那么这时候我们上面求的就是 3 号水块的面积,而 1 和 2 水块在之前进栈操作中就已经求出来了, 4 水块的话在之后(q 出栈,p 和 i 进行比较)也会被计算到。

时间复杂度 O(n) ,空间复杂度 O(n) ,需要扫描一遍数组,但是每个元素会入栈再出栈,所以操作次数和方法1其实是一样的。

方法3(双指针优化方法1)

方法 1 中,我们需要用到一个额外数组来保存左右两边的最大值,其实我们可以用双指针法来规避这个问题。

考虑用两个指针 l 和 r 分别从最左和最右端往中间靠拢,同时用 lmax 记录 l 左边的最高高度,用 rmax 记录 r 右边的最高高度。

此时如果 h[l] < h[r] ,那么我们计算 l 处能蓄水多高,如果 h[l] \ge h[r] ,我们计算 r 处蓄水多高。这样我们时刻只计算低的那边的答案,就能保证 l 两边的最高处较小值一定是 lmax ,r 两边同理。为什么呢?你模拟一遍左右切换的过程就会发现,当 h[l] > h[r] 的时候,切换到计算 r 那边去了,再继续等到 h[r] > h[l] 的时候,又切回计算 l 这边了,所以两端 l 和 r 的值始终保证:当它固定不动,计算另一端高度时,它一定是这一边最高的。

那么如果 h[l] < h[r] ,我们怎么计算 h[l] 处蓄水多高呢?如果 h[l] \ge lmax ,那么 l 处根本就没法蓄水,因为它是最高的,所以更新 lmax 就行了。否则的话 l 两边最大高度较小值一定是 lmax ,还是按照方法 1 那样计算就行了。

这样的话,就不需要额外维护一个高度数组了。时间复杂度 O(n) ,空间复杂度 O(1)

代码

方法1(c++)

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        vector<int> lmax(n+1, 0);
        for (int i = 0; i < n; ++i) {
            lmax[i+1] = max(height[i], lmax[i]);
        }
        int rmax = 0, res = 0;
        for (int i = n-1; i >= 0; --i) {
            rmax = max(rmax, height[i]);
            res += min(lmax[i+1], rmax) - height[i];
        }
        return res;
    }
};

方法2(c++)

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size(), res = 0;
        stack<int> st;
        for (int i = 0; i < n; ++i) {
            while (!st.empty() && height[i] > height[st.top()]) {
                int mid = st.top();
                st.pop();
                if (st.empty()) break;
                res += (min(height[st.top()], height[i]) - height[mid]) * (i - st.top() - 1);
            }
            st.push(i);
        }
        return res;
    }
};

方法3(c++)

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size(), res = 0;
        int l = 0, r = n-1, lmax = 0, rmax = 0;
        while (l < r) {
            if (height[l] < height[r]) {
                if (height[l] >= lmax) lmax = height[l];
                else res += lmax - height[l];
                l++;
            } else {
                if (height[r] >= rmax) rmax = height[r];
                else res += rmax - height[r];
                r--;
            }
        }
        return res;
    }
};

方法1(python)

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        lmax = [0] * (n+1)
        for i in range(n):
            lmax[i+1] = max(height[i], lmax[i])
        rmax, res = 0, 0
        for i in range(n-1, -1, -1):
            rmax = max(rmax, height[i])
            res += min(lmax[i+1], rmax) - height[i]
        return res

方法2(python)

class Solution:
    def trap(self, height: List[int]) -> int:
        n, res = len(height), 0
        st = []
        for i in range(n):
            while len(st) != 0 and height[i] > height[st[-1]]:
                mid = st[-1]
                st.pop()
                if len(st) == 0:
                    break
                res += (min(height[st[-1]], height[i]) - height[mid]) * (i - st[-1] - 1)
            st.append(i)
        return res

方法3(python)

class Solution:
    def trap(self, height: List[int]) -> int:
        n, res = len(height), 0
        l, r, lmax, rmax = 0, n-1, 0, 0
        while l < r:
            if height[l] < height[r]:
                if height[l] >= lmax:
                    lmax = height[l]
                else:
                    res += lmax - height[l]
                l += 1
            else:
                if height[r] >= rmax:
                    rmax = height[r]
                else:
                    res += rmax - height[r]
                r -= 1
        return res

后记

这题方法还是很多的,最好需要画个示意图,模拟一下运行过程。

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 202,980评论 5 476
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,178评论 2 380
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 149,868评论 0 336
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,498评论 1 273
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,492评论 5 364
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,521评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,910评论 3 395
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,569评论 0 256
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,793评论 1 296
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,559评论 2 319
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,639评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,342评论 4 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,931评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,904评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,144评论 1 259
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,833评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,350评论 2 342

推荐阅读更多精彩内容

  • 题目描述(困难难度) 黑色的看成墙,蓝色的看成水,宽度一样,给定一个数组,每个数代表从左到右墙的高度,求出能装多少...
    windliang阅读 542评论 0 0
  • 第5章 引用类型(返回首页) 本章内容 使用对象 创建并操作数组 理解基本的JavaScript类型 使用基本类型...
    大学一百阅读 3,204评论 0 4
  • 我是芳巧,一个终身学习者,这是我的个人原创第101篇原创。学习的路很长我已经开始慢慢走上。。。期待你的齐肩并行。 ...
    梦铁凝阅读 482评论 1 4
  • Quartz 2D是2D绘图引擎,适用iOS和Mac OS X程序。它提供底层轻量级的接口,并且会根据输出显示设备...
    立刻就爽阅读 213评论 0 1
  • 52周挑战计划,第12周复盘(3/19-3/25) 上周目标:每天看美妆类文章 why:要做精致的猪猪女孩 wha...
    小森林Sherry阅读 81评论 0 0