积水问题 一维及二维解法

积水问题是一种经典的计算机科学问题，通常出现在算法面试和编程竞赛中。它涉及到寻找二维或一维数组中的“洼地”，并计算在虚拟降雨后能够蓄积的水量。这里我们将详细探讨一维和二维积水问题的解决方案。 对于一维积水问题，如Twitter面试中的水沟积水问题，给定一个表示不同高度的墙的数组，我们需要找出所有可以蓄水的地方并计算总面积。有两种主要的解法： 1. **递归/分治法**：首先找到数组中的最大高度，然后分别从数组的两端开始遍历，每次遇到较高的墙就计算当前区间的积水。这种方法需要多次递归，效率较低，但逻辑直观。 ```cpp int volume(int a[], int n) { int Left_Max = a[0]; int Right_Max = a[n - 1]; int i = 0, j = n - 1, vol = 0; while (i < j) { if (Left_Max < Right_Max) { ++i; if (Left_Max < a[i]) Left_Max = a[i]; else vol += Left_Max - a[i]; } else { --j; if (Right_Max < a[j]) Right_Max = a[j]; else vol += Right_Max - a[j]; } } return vol; } ``` 2. **双指针法**：从数组的两端同时开始遍历，左边的指针记录当前位置的最大高度（Left_Max），右边的指针记录右边界的最大高度（Right_Max）。在遍历过程中，比较两者高度并更新积水体积，直到两个指针相遇。这种方法效率更高，时间复杂度为O(n)。 在二维积水问题中，我们考虑一个n×n的矩阵，每个单元格表示地形的高度。计算整个矩阵的积水总量，可以采用递归或迭代的方式来解决。基本思想是从矩阵的中心开始，逐行逐列地计算每个子矩阵的积水，直到遍历完整个矩阵。 ```cpp void volume(const int a[MAX_COL_ROW][MAX_COL_ROW], int center) { int Left_Max = 0; int Upper_Max = 0; int Right_Max = 0; int Under_Max = 0; //...（此处继续计算每个方向的最大高度，然后计算积水） } ``` 在这个二维问题中，我们可以将一维问题的Left_Max和Right_Max扩展为四个方向：Left_Max（左边界最大高度）、Upper_Max（上边界最大高度）、Right_Max（右边界最大高度）和Under_Max（下边界最大高度）。每次计算一个单元格的积水时，我们检查其四周的高度，根据边界情况更新最大高度，然后计算积水。 总结来说，积水问题的核心在于识别可以积水的区域并计算其容量。对于一维问题，双指针法是更优的解决方案，而对于二维问题，我们可以从中心向外扩展，逐行逐列地计算积水。这些方法都基于数组或矩阵的特性，巧妙地利用了动态规划和空间搜索策略来高效解决问题。