By Long Luo

Leetcode 407. 接雨水 II 题目如下：

407. 接雨水 II

给你一个 \(m \times n\) 的矩阵，其中的值均为非负整数，代表二维高度图每个单元的高度，请计算图中形状最多能接多少体积的雨水。

示例 1:

输入: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]] 输出: 4 解释: 下雨后，雨水将会被上图蓝色的方块中。总的接雨水量为1+2+1=4。

示例 2:

输入: heightMap = [[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]] 输出: 10

提示: m == heightMap.length n == heightMap[i].length 1 <= m, n <= 200 0 <= heightMap[i][j] <= 2 * 10^4

这道题是 42. 接雨水 的3D版本，区别于2D版本只需要维护左右两个最高的木板，这里需要维护一个围栏，用堆（优先队列）来维护周围这个围栏中的最小元素。

方法一：优先队列 + 最小堆

思路与算法：

因为需要维护一个圈，用来存储水，所以需要从矩阵的最外围往里面遍历，不断缩小圈，直到遍历每个方块，在这个过程中计算每个方块能装多少水，更新 \(\textit{ans}\) 。

那么什么方块能存水呢？

• 该方块不是在圈外；
• 该方块高度比其上下左右四个相邻的方块接水后的高度都要低。

假设方块的索引为 \((i,j)\)，方块高度为 \(\textit{heightMap}[i][j]\)，方块接水后的高度为 \(\textit{water}[i][j]\)，则方块 \((i,j)\) 的接水后的高度为：

\[ \textit{water}[i][j] = \max( \textit{heightMap}[i][j], \min( \textit{water}[i-1][j], \textit{water}[i+1][j], \textit{water}[i][j-1], \textit{water}[i][j+1])) \]

每个方块 \((i,j)\) 实际接水量为：\(\textit{water}[i][j] - \textit{heightMap}[i][j]\)。

那问题变成了如何知道每个方块的 \(\textit{water}[i][j]\) 呢？

1. 因为最外层的方块无法接水，所以最外层的方块接水后的高度 \(\textit{water}[i][j]=\textit{heightMap}[i][j]\)；

2. 根据木桶原理，而每层水的高度则取决于每层方块中高度最低的方块；

3. 从矩阵的四周边界开始，则可以知道最外层方块接水后的高度最小值。之后遍历每层中的每个方块周围\(4\) 个方块，如果比当前方块低，那么说明这个方块可以接水，接水后的高度就是当前层的最小高度，反之更高的话，将其加入优先队列中；

4. 更新最外层的方块标记，在新的最外层的方块再次找到接水后的高度的最小值，依次迭代直到求出所有的方块的接水高度，即可知道矩阵中的接水容量。

By Long Luo

Leetcode 42. 接雨水 题目如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

42. 接雨水

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

示例 1：

![接雨水 1](https://www.longluo.me/assets/blog/images/leetcode/leetcode_42_trapping_rain_water.png)

输入：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
 
提示：
n == height.length
1 <= n <= 2 * 10^4
0 <= height[i] <= 10^5

方法一： 按列求（木桶原理）

思路与算法：

很容易想到，装水的多少，根据木桶原理，只需要关注左边最高的木板和右边最高的模板中较矮的一个就够了，那么存储的水，等于两边木板的较小值减去当前高度的值。

1. 从左向右遍历数组：
   • 从当前元素向左扫描并更新：\(\text{max\_left}=\max(\text{max\_left}, \text{height}[j])\)
   • 从当前元素向右扫描并更新：\(\text{max\_right}=\max(\text{max\_right}, \text{height}[j])\)
2. 更新 \(\text{ans} += \min(\text{max\_left}, \text{max\_right}) - \text{height}[i]\) 。

代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public static int trap(int[] height) {
    if (height == null || height.length <= 2) {
        return 0;
    }

    int ans = 0;
    int len = height.length;
    for (int i = 1; i < len - 1; i++) {
        int maxRight = 0;
        int maxLeft = 0;
        for (int right = i; right < len; right++) {
            maxRight = Math.max(maxRight, height[right]);
        }

        for (int left = i; left >= 0; left--) {
            maxLeft = Math.max(maxLeft, height[left]);
        }

        ans += Math.min(maxLeft, maxRight) - height[i];
    }

    return ans;
}

复杂度分析：

• 时间复杂度：\(O(n^2)\) ，遍历每一列需要 \(n\)，找出左边最高和右边最高的木板加起来刚好又是一个 \(n\)，所以是 \(n^2\)。
• 空间复杂度：\(O(1)\) 。

方法二：按行求

思路与算法：

求第 \(i\) 层的水，遍历每个位置，如果当前的高度小于 \(i\)，并且两边有高度大于等于 \(i\) 的，说明这个地方一定有水，水就可以加 \(1\)。

如果求高度为 \(i\) 的水，首先用一个变量 \(water\) 保存当前累积的水，初始化为 \(0\)。从左到右遍历墙的高度，遇到 \(h \ge i\) 的时候，开始更新 \(water\) 。

第一次遇到已经开始计算时并且 \(h < i\) 的就把 \(water+1\) ，再次遇到 \(h \ge i\) 的，说明这个地方一定有水，就把 \(water\) 加到最终的答案 \(ans\) 里， \(water=0\) ， \(flag=false\) ，然后继续循环。

代码如下所示：

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

public static int trap_row(int[] height) {
    if (height == null || height.length <= 2) {
        return 0;
    }

    int ans = 0;
    int len = height.length;
    int maxHeight = 0;

    for (int x : height) {
        maxHeight = Math.max(maxHeight, x);
    }

    for (int i = 1; i <= maxHeight; i++) {
        boolean flag = false;
        int water = 0;
        for (int j = 0; j < len; j++) {
            if (flag && height[j] < i) {
                water++;
            }

            if (height[j] >= i) {
                ans += water;
                water = 0;
                flag = true;
            }
        }
    }

    return ans;
}

复杂度分析：

• 时间复杂度：\(O(maxHeight \times n)\)，其中 \(maxHeight\) 是数组元素的最大值。
• 空间复杂度：\(O(1)\)。

By Long Luo

1. 冒泡排序(Bubble Sort)

思路与算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public static int[] bubbleSort(int[] nums) {
    if (nums == null || nums.length <= 1) {
        return nums;
    }

    int len = nums.length;
    for (int i = len - 1; i >= 0; i--) {
        boolean isSorted = true;
        for (int j = 0; j < i; j++) {
            if (nums[j] > nums[j + 1]) {
                isSorted = false;
                int temp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = temp;
            }
        }
        if (isSorted) {
            break;
        }
    }

    return nums;
}

复杂度分析：

• 时间复杂度：\(O(N^2)\)，其中 \(N\) 是数组 \(\textit{nums}\) 的长度。
• 空间复杂度：\(O(1)\)。

2. 选择排序(Select Sort)

思路与算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

public static int[] selectSort(int[] nums) {
    if (nums == null || nums.length <= 1) {
        return nums;
    }

    int len = nums.length;
    for (int i = 0; i < len; i++) {
        for (int j = i + 1; j < len; j++) {
            if (nums[j] < nums[i]) {
                int temp = nums[j];
                nums[j] = nums[i];
                nums[i] = temp;
            }
        }
    }

    return nums;
}

复杂度分析：

• 时间复杂度：\(O(N^2)\)，其中 \(N\) 是数组 \(\textit{nums}\) 的长度。
• 空间复杂度：\(O(1)\)。

By Long Luo

一

国庆假期中午吃完饭后给老爸打了个电话，却是姐姐接的。姐姐说，老爸还在山上摘茶籽，都还没有吃饭。姐姐是回家拿蛇皮袋去装茶籽的，等下还要去山上装完茶籽再回家。那到吃饭时都还要一个多小时后了，吃完饭还要去山上摘茶籽。

想到爸爸在家干活时腿不小心受伤了，现在还拖着腿一瘸一拐在山上摘茶籽。在手机上查了下天气，老家现在还是37°的高温，而我在深圳31°时在家里都还要吹空调，心里觉得自己太不孝了。

妈妈说我国庆假期应该回老家去摘茶籽的，不吃点苦都不会体谅父母的辛苦，要不然在家都懒成啥样了。明年国庆一定要回去摘茶籽，吃吃苦，体验下生活。

突然触动起了小时候关于山茶树的一些回忆。

二

茶籽是什么？很多人是不知道的。但要说到现在大做广告的山茶油，大家就知道了，茶油就是由山茶籽压榨加工而来的，南方80后小时候日常食用的就是山茶油。

茶籽树又叫油茶树，是一种常绿的小乔木。因为它结的果实可以榨油，故叫油茶树。收割完第二季稻子之后，大概霜降时，成熟的茶籽的挂满枝头，像点缀了胭脂的玛瑙一样，沉甸甸的挂在枝头，把树枝都压弯了，煞是好看，看着就令人高兴，或许这就是丰收的喜悦吧！

茶籽树长的很慢，树杆木质十分细密，非常紧实。大多长的不高，茶籽都好摘。够得着的站在地上摘，够不着的爬上树去摘。

早晨是一天采摘中的最佳时辰，天刚亮不久全家一起出发了。采茶籽动作单一，但工作量很大。茶籽数量众多，而且太阳烤背，往往会汗如雨下。一两个小时过后，一家人就摘了几个蛇皮袋，这时到了送袋子回去做饭的时间。刚摘下来的油茶籽重，一般用自行车或者手推车运回家。

送回家之后还要做好饭菜带进山来。在山里吃饭其实是一件很诱惑人的事，吃起来特别的香。

三

茶籽全部采摘回来以后，就要晒茶籽了。秋天的太阳温度一般没有夏天那么毒，所以茶籽要晒上好几天才行。

晒过几天太阳，茶籽壳便会破裂，露出里面乌黑的茶仁。但只有少数茶籽壳会破裂，其他的都要人工剥开茶籽壳，取出里面一颗颗圆形或扁圆形的茶籽了。

这项工作主要是闲暇时做，印象中小学时吃完饭看电视时，一家人一边看着电视，一边剥茶籽。因为只有晚上才有时间去剥茶籽，所以剥茶籽这项也要做挺久的。读书时也挺讨厌的，因为做完作业没法出去玩了。剥下的茶籽壳可以用作烧柴的燃料，烧火做饭时用，不过大多是冬天放在火笼里。

最后，爸爸会用小推车把茶籽送到附近的油坊去榨油，我也会跟着去。在榨房里，先用机器将茶籽粉碎，入木甑蒸一定时间。出甑后，将原料填入用稻草垫底的圆形铁箍中，制成榨油用的茶籽饼，最后将一块块菜饼整齐地横放进主榨的榨槽内，用木枋挤紧，茶籽饼在巨大压力下从榨河的槽眼流出茶籽油。

茶籽榨油后留下的油饼，也叫“茶枯”，也叫茶麸、茶籽饼，是油茶籽经榨油后的渣饼，我们小时候经常用它敲的粉碎，放在热水里，拿去药鱼。因为这种水呈碱性，而鱼无法忍受，就会因为缺氧而浮出水面。

By Long Luo

The Solutions of LeetCode热题 100 | Top 100 Liked Questions: