leetcode42：接雨水

题目链接

leetcode

题目描述

给定 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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

void printArray(const vector<int>& nums) {
    cout << "[";
    for (const int& num : nums) {
        cout << num << ",";
    }
    cout << "]" <<endl;
}

/*
    暴力解法，TLE
    对于每个柱子 i，遍历数组分别找到左边和右边最高的柱子，计算雨水量。

    时间复杂度：O(n^2)
        其中 n 是数组的长度。遍历数组三次。
    空间复杂度：O(1) 
*/
class Solution_0 {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        int res = 0;
        for (int i = 0; i < n - 1; i ++) {
            int l_max = 0, r_max = 0;
            // 找右边最⾼的柱⼦
            for (int j = i; j < n; j ++) {
                r_max = max(r_max, height[j]);
            }
            // 找左边最⾼的柱⼦
            for (int j = i; j >= 0; j --) {
                l_max = max(l_max, height[j]);
            }
            // 更新当前的雨水量
            res += min(l_max, r_max) - height[i];
        }

        return res;
    }
};

/*
    观察整个图形，对水的面积按列进行拆解。
    每个矩形条上方接到水的高度，是由它左边矩形，和右边矩形决定的。

    两个数组 r_max 和 l_max 充当备忘录，
        l_max[i] 表⽰位置 i 左边最⾼的柱⼦⾼度，
        r_max[i] 表⽰位置 i 右边最⾼的柱⼦⾼度。 
    预先把这两个数组计算好，避免重复计算。
    最后统计答案：第 i 个矩形条，接到雨水量为 min(l_max[i], r_max[i]) - height[i]。

    时间复杂度：O(n)
        其中 n 是数组的长度。遍历数组三次。
    空间复杂度：O(n) 
        两个数组分别记录每个位置左边和右边的高度。
*/
class Solution_1 {
public:
    int trap(vector<int>& height) {
        if (height.empty()) return 0;
        int n = height.size();

        // 数组充当备忘录
        vector<int> l_max(n), r_max(n);
        // 初始化 base case
        l_max[0] = height[0];
        r_max[n - 1] = height[n - 1];
        // 从左向右计算 l_max
        for (int i = 1; i < n; i ++) {
            l_max[i] = max(l_max[i - 1], height[i]);
        }
        // 从右向左计算 r_max
        for (int i = n - 2; i >= 0; i --) {
            r_max[i] = max(r_max[i + 1], height[i]);
        }

        // 计算雨水量
        int res = 0;
        for (int i = 0; i < n; i ++) {
            res += min(l_max[i], r_max[i]) - height[i];
        }
        
        return res;
    }
};

/*
    一个位置的储水量取决于左右高度中较低的那个。

    这次不使用备忘录提前计算，⽤双指针边⾛边算，节省下空间复杂度。
    初始化时，将左右指针放在最左边、最右边，每次移动高度较低的指针（瓶颈）。
    若移动后的高度变大，则当前位置不能存水，更新边界高度；
    若移动后的高度变小，则当前位置可以存水，计算存水量并更新答案。

    时间复杂度：O(n)
        其中 n 是数组的长度。遍历数组一次。
    空间复杂度：O(1)
        使用了几个变量。
*/
class Solution {
public:
    int trap(vector<int>& height) {
        if (height.empty()) return 0;
        int n = height.size();

        int res = 0;
        int l = 0, r = n - 1;
        int l_max = height[0], r_max = height[n - 1];
        while (l <= r) {
            l_max = max(l_max, height[l]);
            r_max = max(r_max, height[r]);
            // 计算雨水量
            if (l_max < r_max) {
                res += l_max - height[l];
                l ++;
            } else {
                res += r_max - height[r];
                r --;
            }
        }

        return res;
    }
};

/*
    维护一个单调栈，存储的是索引。
    遍历数组，对于每个柱子：
        若栈不为空且当前柱子高度大于栈顶柱子高度，则弹出栈顶柱子并计算其接水量。
        否则，将当前柱子的索引入栈。
    计算接水量：
        stk.top()、top 与 i 三个位置构成一个 U 型，
        其中 top 位置代表 U 型的底部，计算出该 U 型可以接水的面积。

    时间复杂度：O(n)
        其中 n 是数组的长度。遍历数组一次。
    空间复杂度：O(n)
        存储单调栈的空间 O(n)。

    参考：https://www.acwing.com/solution/content/121/
*/
class Solution_3 {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        if (n <= 2) return 0;

        int res = 0;
        stack<int> stk;
        for (int i = 0; i < n; i ++) {
            // 当前高度大于栈顶元素的高度时，计算可以接的雨水量
            while (!stk.empty() && height[i] > height[stk.top()]) {
                int top = stk.top(); stk.pop();
                // 若栈为空，则说明没有左边界，无法形成凹槽
                if (stk.empty()) break;
                // 计算宽度和高度
                int w = i - stk.top() - 1;
                int h = min(height[i], height[stk.top()]) - height[top];
                res += w * h;
            }
            // 当前索引入栈
            stk.push(i);
        }

        return res;
    }
};

int main() {
    Solution solution;
    vector<vector<int>> testCases = {
        {0,1,0,2,1,0,1,3,2,1,2,1},
        {4,2,0,3,2,5}
    };

    for (auto& nums : testCases) {
        cout << "Input: ";
        printArray(nums);
        cout << "Input: " << solution.trap(nums) << endl;
    }
    
    return 0;
}

Golang 代码

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
package main

import "fmt"

// max 返回两个整数中的较大值
func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

// min 返回两个整数中的较小值
func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

/*
    每个矩形条上方接到水的高度，是由它左边矩形，和右边矩形决定的。

    两个数组 r_max 和 l_max 充当备忘录，
        l_max[i] 表⽰位置 i 左边最⾼的柱⼦⾼度，
        r_max[i] 表⽰位置 i 右边最⾼的柱⼦⾼度。 
    预先把这两个数组计算好，避免重复计算。
    最后统计答案。

    时间复杂度：O(n)
        其中 n 是数组的长度。遍历数组三次。
    空间复杂度：O(n) 
        两个数组分别记录每个位置左边和右边的高度。
*/
func trap_0(height []int) int {
    n := len(height)
    if n == 0 {
        return 0
    }

    // l_max[i] 表示从左边到第 i 个位置的最大高度
	// r_max[i] 表示从右边到第 i 个位置的最大高度
    l_max := make([]int, n)
    r_max := make([]int, n)
    // 初始化
    l_max[0] = height[0]
    for i := 1; i < n; i ++ {
        l_max[i] = max(l_max[i-1], height[i])
    }
    r_max[n-1] = height[n-1]
    for i := n-2; i >= 0; i -- {
        r_max[i] = max(r_max[i+1], height[i])
    }

    // 计算雨水量
    res := 0
    for i := 0; i < n; i ++ {
        res += min(l_max[i], r_max[i]) - height[i]
    }
    return res
}

/*
    双指针从数组的两端向中间移动，同时维护左边和右边的最大高度。
    在每次移动时，计算当前位置能接多少雨水，并累加到结果中。
         
    时间复杂度：O(n)
        遍历数组一次
    空间复杂度：O(1)
*/
func trap(height []int) int {
    n := len(height)
    if n == 0 {
        return 0
    }

    // l 表示数组的起始位置，r 表示数组的结束位置
    l, r := 0, n-1
    // l_max, r_max 分别表示从左到右遍历时遇到的最大高度，从右到左遍历时遇到的最大高度
    l_max, r_max := 0, 0
    res := 0

    for l < r {
        l_max = max(l_max, height[l])
        r_max = max(r_max, height[r])
        // 计算当前位置可以接的雨水量
        if height[l] < height[r] {
            res += l_max - height[l]
            l ++
        } else {
            res += r_max - height[r]
            r --
        }
    }

    return res
}

/*
    初始化栈：
        使用一个栈（stack）来存储柱子的索引，栈内柱子的高度保持单调递减。
        这样可以通过索引快速计算宽度。
    遍历高度数组，对于每个柱子：
        若栈不为空，并且当前柱子高度大于栈顶柱子高度，则弹出栈顶柱子并计算接水量。
        否则，将当前柱子的索引入栈。
    累加雨水量：
        每次计算的雨水量累加到结果中。

    时间复杂度：O(n)
        其中 n 是数组的长度。遍历数组一次。
    空间复杂度：O(n)
        存储单调栈的空间 O(n)。
*/
func trap_2(height []int) int {
    stack := []int{}
    res := 0

    for i := 0; i < len(height); i ++ {
        // 当前高度大于栈顶元素的高度时，计算可以接的雨水量
        for len(stack) > 0 && height[i] > height[stack[len(stack)-1]] {
            // 弹出栈顶元素
            top := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            // 如果栈为空，说明没有左边界，无法形成凹槽
            if len(stack) == 0 {
                break
            }

            // 计算雨水量
            left := stack[len(stack)-1]
            w := i - left - 1
            h := min(height[i], height[left]) - height[top]
            res += w * h
        }
        // 将当前柱子的索引入栈
        stack = append(stack, i)
    }

    return res
}

func main() {
    // 测试用例
    testCases := []struct {
        height   []int
        expected int
    }{
        {[]int{0,1,0,2,1,0,1,3,2,1,2,1}, 6},
        {[]int{4,2,0,3,2,5}, 9},
    }

    for i, tc := range testCases {
        result := trap(tc.height)
        fmt.Printf("Test Case %d, Input: height = %v\n", i+1, tc.height)
        if result == tc.expected {
            fmt.Printf("Test Case %d, Output: %d, PASS\n", i+1, result)
        } else {
            fmt.Printf("Test Case %d, Output: %d, FAIL (Expected: %d)\n", i+1, result, tc.expected)
        }
    }
}
#leetcode
leetcode42：接雨水
https://lcf163.github.io/2023/10/23/leetcode42：接雨水/
作者
乘风的小站
发布于
2023年10月23日
许可协议