算法leetcode

【多解法】力扣42-接雨水

字数统计: 1.4k字   |   阅读时长: 6分
, , , ,

摘要: 接雨水问题的各种解法

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文我们看一个几年前就被网上研究透了的陈题：接雨水。不过从一题多解的角度，本题还是值得看一下的，几个算法都是非常主流的算法：

  • 算法1：单调栈
  • 算法2：动态规划
  • 算法3：双指针
  • 算法4：减治

$1 题目

给定 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

提示：

1
2
3
n == height.length
1 <= n <= 2 * 1e4
0 <= height[i] <= 1e5

$2 题解

算法1: 单调栈

单调栈的原理参考 单调栈。

维护一个单调递减的栈：栈内保存的是下标 i，从栈底到栈顶，height[i] 单调递减。对于栈里相邻的两个下标，靠近栈底的下标是靠近栈顶的下标左侧第一个比它大的位置。

从小到大枚举下标 i，将栈里比 height[i] 小的下标弹出去，假设弹出的下标是 j，则可以更新一部分面积，宽度是栈里的下一个下标 k 与 i 的距离 (i - k - 1)，高度是准备压入的 height[i] 与栈底 max_h 的较小值减去 height[j]。

每个下标都要经历一次进栈出栈，将每次出栈时更新的面积累加起来就得到答案。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int trap(vector<int>& height) {
        if(height.empty()) return 0;
        int n = height.size();
        if(n <= 2) return 0;
        stack<int> st;
        int ans = 0;
        for(int i = 0; i < n; ++i)
        {
            while(!st.empty() && height[st.top()] <= height[i])
            {
                int j = st.top();
                st.pop();
                if(st.empty())
                    break;
                int k = st.top();
                ans += (i - k - 1) * (min(height[k], height[i]) - height[j]);
            }
            st.push(i);
        }
        return ans;
    }
};

算法2: 预处理前缀状态

对每个 i，预处理出：

1
2
lh[i]: i 左边的最高值
rh[i]: i 右边的最高值

预处理的过程是动态规划，转移方程如下：

1
2
lh[i] = max(lh[i - 1], h[i - 1]), max 有结合律，可以从左往右扫
rh[i] = max(rh[i + 1], h[i + 1]), 类似地, rh 从右往左扫

这种思路有点类似于前缀状态的预处理，只是这里的状态是前缀最值和后缀最值。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int trap(vector<int>& height) {
        if(height.empty()) return 0;
        int n = height.size();
        if(n <= 2) return 0;
        vector<int> lh(n, 0); // 0,[1..n],n+1
        vector<int> rh(n, 0);
        for(int i = 1; i <= n - 1; ++i)
            lh[i] = max(lh[i - 1], height[i - 1]);
        for(int i = n - 2; i >= 0; --i)
            rh[i] = max(rh[i + 1], height[i + 1]);
        int result = 0;
        for(int i = 1; i < n - 1; ++i)
        {
            int hw = min(lh[i], rh[i]);
            if(height[i] < hw)
                result += hw - height[i];
        }
        return result;
    }
};

算法3: 双指针

从两个端点向里收缩，维护左右端点指针l=0, r=n-1和左高右高。

收缩时向内推进高度较低的哪个指针，对比推进之后的值与推进之前的值。

如果变大了，则更新响应的左高或右高。

如果变小了，则推进之后的位置可以容纳雨水，高度就是当前左高右高中较小的。

二维接雨水问题的解法在思路上与一维的双指针做法相同。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    int trap(vector<int>& height) {
        if(height.empty()) return 0;
        int n = height.size();
        if(n <= 2) return 0;
        int lh = height[0], rh = height[n - 1];
        int left = 0, right = n - 1;
        int result = 0;
        while(left < right)
        {
            if(lh <= rh) // 向右移动 left
            {
                ++left;
                if(height[left] < lh)
                    result += lh - height[left];
                else if(height[left] > lh)
                    lh = height[left];
            }
            else // 向左移动 right
            {
                --right;
                if(height[right] < rh)
                    result += rh - height[right];
                else if(height[right] > rh)
                    rh = height[right];
            }
        }
        return result;
    }
};

算法4: 减治

1
2
3
4
5
6
7
8
原问题区间 [left, right] 

可以直接解决的情况: right - left <= 1 时可以直接解决，答案为 0

找到 [left, right] 上最大值位置 m1 和次大值位置 m2
[min(m1, m2), max(m1, m2)] 上的问题可以直接解决，答案为 (abs(m1 - m2) - 1) * A[m2]

减治: 子问题变为 [left, min(m1, m2)], [max(m1, m2), right]

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        return solve(height, 0, n - 1);
    }

private:
    int solve(const vector<int>& h, int l, int r)
    {
        if(r - l <= 1)
            return 0;
        int m1 = -1, m2 = -1;
        int max1 = INT_MIN, max2 = INT_MIN;
        for(int i = l; i <= r; ++i)
        {
            if(h[i] > max1)
            {
                max2 = max1;
                m2 = m1;
                max1 = h[i];
                m1 = i;
            }
            else if(h[i] > max2)
            {
                max2 = h[i];
                m2 = i;
            }
        }
        int ans = (abs(m1 - m2) - 1) * max2;
        for(int i = min(m1, m2) + 1; i <= max(m1, m2) - 1; ++i)
            ans -= h[i];
        ans += solve(h, l, min(m1, m2));
        ans += solve(h, max(m1, m2), r);
        return ans;
    }
};
Share