Leetcode经典题目——接雨水的渐进式思考

前言接雨水作为leetcode上一道经典的hard题在我第一次看到的时候曾自信的可以靠自己做出来最优的算法那时还问豆包只告诉我这道题最优的时间和空间复杂度我来自己想结果想了好几个小时从下午到晚上最后无奈选择了暴力算法。后面在对题解进行研究后发现了这算法的得来不是一蹴而就的而是渐进的有迹可循的。接下来我将重点展示思路的迭代与优化通过这个怎么让我们想到好的算法最终抵达。希望可以对看完这篇文章的读者在面对未来相似的题目时会有帮助。题目介绍First.暴力算法我最初暴力算法介绍正所谓“九层之台起于累土。千里之行始于足下。”暴力算法只是最原始的算法不是最“坏”的算法正是通过暴力算法我们才可以在过程中发现哪些是阻碍我们时间复杂度的点从而优化。我的算法是原始暴力的。对于height数组中每个数都减去一统计每一次在两个正数还包括0之间的负数数目每一次的结果累加就是结果。这样做不仅时间复杂度飞起在最后几个测试用例 时间太长坠机了而且带来了复杂的边界条件控制一不谨慎就是报错。int trap(int* height, int heightSize) { 暴力 //特殊情况讨论 if(heightSize1) return 0; //初始化变量 int move0; int waternum0; int new_waternum0; int posnum2; //主循环 while(posnum2) { posnum0; while(moveheightSize) { height[move]--; if(height[move]0) { posnum; } move; } move0; while(moveheightSize-2) { if(height[move]0height[move1]0) { new_waternum; move; while(moveheightSize-2height[move1]0) { move; new_waternum; } } else { move; } if(height[move]0) { waternumnew_waternum; new_waternum0; } } if(height[move1]0) { waternumnew_waternum; } move0; new_waternum0; } //return return waternum; }显然这个算法不是好算法但通过这个我们能发现有可优化的点这个算法实际上来说是对每一块空间都进行了处理判断其是不是水。我们要做的是优化算法目光就要从局部走向全局根据题目本身总结一般规律数学用大的视角去看待问题。用数学来优化暴力算法根据我们学的知识自然会知道水往低处流和木桶效应两大规则。水不会在高处盘踞水最高高度只取决于木桶最矮的一块木板。那么对应于题目我们可以将一块块凹陷的“盆地”看成是一个木桶因为水往低处流其只会在形如“盆地”这种才会驻留。盆地顾名思义就是两边的高度要高于中间高度。那么我们假设从m到q是盆地mq他们的高度分别为h(m)和h(q)根据以上所述我们可以遍历m到q。然后就可以的出其中每个柱子的高度累加得到其中所有柱子数目和设为sum。然后算(n-q)得到盆地的跨度min( h(m),h(q) )我们就可以计算出盆地最大有效储水高度,减去sum从而我们可以计算出一块盆地的总储水量。重复此操作累加我们就可以算出题目中所有的可以储水的量可喜可贺可喜可贺。但真正上手操作的时候我们就会发现站在我们的上帝视角我们可以轻而易举的就看到q和m的具体方位。但是在真正的落地实施的过程中计算机很难一次就知道哪个是m,哪个是q。有很多难以解决的复杂的情况。让我们这个思路无法简单的实施。所以。我们的想法和真正可以落地实施的算法是会有一定差距的。难道我们上述的思考就没有意义了吗不。我们可以转换思路从求整个盆地可以储存的水量转向求盆地中一块空间宽度里面可以存储的水量。于是我们就得出了一个公式对于盆地内任意一个x(mxq),其可以存储的水量water_num(x)为:water_num(x) min( h(m) , h(q) ) - h(x)过去思路的葬送成为了我们未来解决这个问题的利剑。那么现在我们的问题就转化为:怎么知道题目中一个又一个可能存在的盆地那么我们就可以遍历从1到n,对于其中的任意一个x我们可以向左遍历一次找到左边的最大值。再向右边遍历一次找到右边的最大值就是找到属于x的m和q。然后根据这个公式就可以算出来对于任意的x的可以储存的水量累加就是整体可以储存的水量。(时间复杂度O(),空间复杂度O(n))。#include stdio.h #include stdlib.h // 用于abs但这里实际用不到主要是max/min // 辅助函数返回两个数中的较大值 int max(int a, int b) { return a b ? a : b; } // 辅助函数返回两个数中的较小值 int min(int a, int b) { return a b ? a : b; } // 计算能接的雨水总量暴力算法 int trap(int* height, int heightSize) { int total_water 0; // 总雨水量 // 遍历每个位置首尾位置无法接雨水直接跳过 for (int i 1; i heightSize - 1; i) { // 1. 找当前位置左侧的最大高度 int left_max 0; for (int j 0; j i; j) { left_max max(left_max, height[j]); } // 2. 找当前位置右侧的最大高度 int right_max 0; for (int j i 1; j heightSize; j) { right_max max(right_max, height[j]); } // 3. 计算当前位置能接的雨水量 int current_water min(left_max, right_max) - height[i]; // 如果结果为正累加否则加0接不到雨水 total_water current_water 0 ? current_water : 0; } return total_water; } // 测试示例 int main() { // 测试用例1经典示例预期输出6 int height1[] {0,1,0,2,1,0,1,3,2,1,2,1}; int size1 sizeof(height1) / sizeof(height1[0]); printf(测试用例1总雨水量%d\n, trap(height1, size1)); // 输出6 // 测试用例2无凹陷预期输出0 int height2[] {1,2,3,4,5}; int size2 sizeof(height2) / sizeof(height2[0]); printf(测试用例2总雨水量%d\n, trap(height2, size2)); // 输出0 // 测试用例3单个凹陷预期输出1 int height3[] {2,0,2}; int size3 sizeof(height3) / sizeof(height3[0]); printf(测试用例3总雨水量%d\n, trap(height3, size3)); // 输出1 return 0; }在此之上的进一步优化空间换时间现在我们的思路已经明了但这个时间复杂度仍然是O()。我们想优化这个时间复杂度。使其的量级降低。我们就可以用经典的思路空间换时间。我们来分析以上主要浪费时间的过程主要是对于每一个x我们都要向左和向右都遍历一次然后来找到最大值。同样我们也知道。它向左向右的最大值都是固定的。因此我们可以创造出一个数组来提前存储这些值。然后需要遍历到x时直接调用这个值就好了。我们的思路具体可以表现为先创建一个数组从左到右遍历。将遇到值与创建的临时变量max_left(代表到当前遍历位置之前最大的柱子的高度)如果遇到更大的就将更大的赋给max_left对于右边同理。然后由于我们是想得到公式中的这个“min( h(m) , h(q) )”我们就可以同时遍历这两个数组取其中较小的一个。存入再开辟的一个数组。最后我们只要遍历x并调用这个数组中的这个值我们就可以得到每个x的储水量累加得出答案。(时间复杂度O(n),空间复杂度O(n))​ int trap(int* height, int heightSize) { int n heightSize; if (n 0) { return 0; } int leftMax[n]; memset(leftMax, 0, sizeof(leftMax)); leftMax[0] height[0]; for (int i 1; i n; i) { leftMax[i] fmax(leftMax[i - 1], height[i]); } int rightMax[n]; memset(rightMax, 0, sizeof(rightMax)); rightMax[n - 1] height[n - 1]; for (int i n - 2; i 0; --i) { rightMax[i] fmax(rightMax[i 1], height[i]); } int ans 0; for (int i 0; i n; i) { ans fmin(leftMax[i], rightMax[i]) - height[i]; } return ans; } 作者力扣官方题解 链接https://leetcode.cn/problems/trapping-rain-water/solutions/692342/jie-yu-shui-by-leetcode-solution-tuvc/ 来源力扣LeetCode 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。 ​最终优化终极思路-真正的原理回归本质我们一开始为什么要采用盆地的这个模型因为盆地它能留得住水它不会让水从中流出去。为什么能留得住水呢因为有一根柱子左或右它大于盆地中所有柱子的高度所以才能留得住水。所以我们可以转换一个思路。我们不一定要求每个x左边是整个的最大值和右边是整个右边的最大值。举个例子我们这时候让一个指针从左向右移。它可以明确确定一个左边的最大值。这时候如果我们能找到右边的一个大于左边的最大值的柱子。就是临时的不一定是在x整个右边最大的也不必要是右边最大值的柱子。那么在x继续向右遍历的过程中只要这个柱子可以大于左边最大的柱子。也就是保证储存在中间的水不会流出来。那么我就可以肆无忌惮的向右边遍历。因为水一定不会流出来。右边临时最高的柱子会保证这个事实。然后由于具体储存水量的多少是取决于两边柱子中较矮的一个也就是说取决于左边的最大值因为在例子中现在右边临时最高的柱子的高度大于左边。因此我们可以直接调用这个左边最高高度来计算每一个遍历的x位置的储水量。那如果在向右遍历过程中碰到了比右边大的我就可以将这个作为左边的临时最大值同上我就可以肆无忌惮的将右边的指针向左一直遍历。这也就是双指针背后的原理。我们追求的不是全局最大而是要能留得住水的“最大”。(时间复杂度O(n),空间复杂度O(1))int trap(int* height, int heightSize) { //双指针 //特殊情况讨论 if(heightSize1) return 0; //初始化变量 int left0; int rightheightSize-1; int left_maxheight[0]; int right_maxheight[right]; int waternum0; //主循环 while(leftright) { if(left_maxright_max) { //算右边 waternumright_max-height[right]; right--; if(height[right]right_max) right_maxheight[right]; } else { //算左边 waternumleft_max-height[left]; left; if(height[left]left_max) left_maxheight[left]; } } return waternum; }结语综上所述我们从最原始。最暴力的算法一步一步走到了最优的算法。其中经历了用数学发现规律空间换时间经典方法还有真正认识到这个问题的本质的这样的一个过程。所以在面对往后相似的题目时我们就多了几个可以走的方向可不可以用数学来概括这个问题的一些的普遍规律可不可以采用空间换时间方法来降低时间的复杂度然后就是对于这个问题我真的理解到本质了吗会不会有更加本质的东西我还未曾探索到。未来的道路十分漫长当下的这个题目或许会成为我们感觉上难以越过去的一道坎感到气馁。但是放到数月后数年后。回望过去。这可能也不过只是一个平凡的土丘。莫以微尘之小浮而失未竟之花海。与诸君共勉以上文章若有任何有误的地方请指正谢谢大家了qwq。