接雨水 - etherwindy

642 words

3 minutes

接雨水

2024-04-20

LeetCode

Algorithms

/

Dynamic Programming

Cover Image Source: Source

题目链接：42. 接雨水

思路#

本题思路有动态规划、单调栈、双指针等，详见官方解答。这里提供一种动态规划和单调栈结合的方法。

总体思路#

雨水面积可表示为

S_{rain} = (S_{rain} + S_{pillar}) - S_{pillar} = S_{total} - S_{pillar}.

$S_{pillar}$ 直接求和可以得出，因此关键在于如何求出 $S_{total}$ 。下面通过动态规划解决这个问题。

动态规划#

用 $dp[i]$ 表示仅存在下标在 $[0, i]$ 之中的柱子时，柱子和雨水的面积之和。考虑添加第 i+1 号柱子。如果 $[0, i]$ 中存在比第 i+1 号柱子更高的柱子，假设第 $front[i+1]$ 号柱子是这些柱子中最靠后的柱子，则

dp[i + 1] = dp[front[i+1]] + (i + 1 - front[i+1])height[i + 1].

如果不存在，则找到 $[0, i]$ 中最高的柱子，假设是第 $k_{i+1}$ 号柱子，则

dp[i + 1] = dp[k_{i+1}] + (i - k_{i+1})height[k_{i+1}] + height[i + 1].

为了区分以上两种情况，用 $front[i] = i$ 表示第 i 号柱子之前不存在更高的柱子。

由此可以得出状态转移方程：

dp[i] = \left\{ \begin{aligned} & dp[i] = dp[front[i]] + (i - front[i])height[], & front[i] \neq i, \\ & dp[i] = dp[k_i] + (i - k_i - 1)height[k_i] + height[i], & otherwise. \end{aligned} \right.

现在最大的问题是如何求出 $front[i]$ 。这里使用单调栈来求解。

单调栈#

从右往左将数列中的元素加入单调递减栈，当单调性不满足时，将栈顶元素弹出直至满足单调性。每轮循环中，对于任意被弹出的元素 a ，新加入的元素 b 即为所有在 a 左侧且比 a 大的元素中距离 a 最近的元素。由此可求得 $front[\cdot]$ 数组。

代码#

代码如下：

1
class Solution {
2
public:
3
    int trap(vector<int> &height) {
4
        int n = height.size();
5
        stack<int> mono; // monotone stack
6
        vector<int> front(height.size(), 0);
7
        vector<int> dp(height.size() + 1, 0);
8
        int sum = 0;  // 高度之和
9
        int maxIndex = 0; // 当前高度最高的柱子
10

11
        // 单调栈
12
        for (int i = n - 1; i >= 0; --i) {
13
            sum += height[i];
14
            front[i] = i;
15
            while (!mono.empty() && height[mono.top()] < height[i]) {
16
                front[mono.top()] = i;
17
                mono.pop();
18
            }
19
            mono.push(i);
20
        }
21

22
        dp[0] = height[0];
23
        for (int i = 1; i < n; ++i) {
24
            if (front[i] < i)
25
                dp[i] = dp[front[i]] + height[i] * (i - front[i]);
26
            else // front[i] == i
27
                dp[i] = dp[maxIndex] + height[maxIndex] * (i - maxIndex - 1) + height[i];
28

29
            maxIndex = height[i] > height[maxIndex] ? i : maxIndex;
30
        }
31

32
        return dp[n - 1] - sum;
33
    }
34
};