| 接雨水的四种姿势 | 您所在的位置：网站首页 › 雨水节气提出的问题 › 接雨水的四种姿势 |
接雨水的四种姿势
|
前言
leetcode 42. 接雨水是一道业内著名的hard题，多次出现在面试场上，经久不衰，难住了一届又一届的候选人。 作为leetcode上热度最高的题目之一，题目评论区也是好一番热闹景象。有人表示看了三天做不出来，有人在评论区洋洋洒洒五六种解法。 其实在这么多的解法中，我们只需要着重掌握双指针和单调栈两种即可。 当然，暴力解法可以不屑，但不能不会。 所有的解法大致可以分为两类：按行求和按列求，所谓按“列”求，是指将雨水部分按列拆分，分别计算数组0位置，1位置，…，n-1位置的答案。
所谓按行求，是指将雨水部分按行拆分成n个部分，然后分别计算每个部分能积攒多少水，最后再将结果汇总。
在本文给出的几种解法中，解法 1、2、3 都是按列求的，解法 4 是按行求的。 题目描述给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 示例 1：
示例 2： 输入：height = [4,2,0,3,2,5] 输出：9 解法一：暴力超出时间限制，不能通过 算法思路逐个计算每一列能存下的水量。 遍历整个数组。针对数组中的每个元素arr[i]，都分别向左、向右遍历一遍数组，找到arr[i]左侧和右侧的最大值，计为leftMax和rightMax，如果leftMax arr[0...i]},max{arr[i...n−1]}}−arr[i] 代码实现 int trap(vector& height) { int sum = 0; int n = height.size(); for (int i=0; i if (height[j] > leftMax) { leftMax = height[j]; } } int rightMax = 0; for (int j=i; j rightMax = height[j]; } } sum += min(leftMax, rightMax) - height[i]; } return sum; } 复杂度分析 时间复杂度： O ( n 2 ) O(n^2) O(n2)空间复杂度： O ( 1 ) O(1) O(1) 解法二：双指针从暴力解法中我们可以看到，要求数组i位置可以存储的水量，需要先求出0到i位置的最大值max(arr[0...i])，再求出i到n-1位置的最大值max(arr[i...n-1])，两个值中取最小与arr[i]做差。 暴力解法之所以时间复杂度比较差，是因为对于数组中的每一个元素，都需要再遍历一遍数组才能得到它左右两侧的最大值。 所以我们可以通过预处理数组得到leftMax[]和rightMax[]两个数组，leftMax[i]代表数组0到i位置的最大值，leftMax[i] = max(leftMax[i-1], arr[i])；rightMax[i]代表数组i位置到n-1位置的最大值，rightMax[i] = max(rightMax[i+1], arr[i])。 这样我们就得到了如下的算法流程。 首先遍历数组，从左向右得到数组leftMax[]，再从右向左得到rightMax[]。然后再遍历一遍数组，对于数组的每一个位置i，通过leftMax[i]，rightMax[i]和arr[i]得到结果，将结果汇总得到的值就是最终答案。 代码实现 C++ int trap(vector& height) { int n = height.size(); vector leftMax(n, 0); leftMax[0] = height[0]; for (int i=1; i rightMax[i] = max(rightMax[i+1], height[i]); } int res = 0; for (int i=0; i int n = height.length; int[] leftMax = new int[n]; leftMax[0] = height[0]; for (int i=1; i rightMax[i] = Math.max(rightMax[i+1], height[i]); } int res = 0; for (int i=0; i n := len(height) leftMax := make([]int, n) leftMax[0] = height[0] for i:=1; i rightMax[i] = max(rightMax[i+1], height[i]) } res := 0 for i:=0; i int n = height.length; int leftMax = 0, rightMax = 0, left = 0, right = n - 1, res = 0; while (left // 左侧结算 res += leftMax - height[left++]; } else if (leftMax > rightMax) { // 右侧结算 res += rightMax - height[right--]; } else { // 双侧结算 res += leftMax - height[left++]; if (left n := len(height) leftMax, rightMax, left, right, res := 0, 0, 0, n-1, 0 for left res += leftMax - height[left] left++ } else if leftMax > rightMax { res += rightMax - height[right] right-- } else { res += leftMax - height[left] left++ if left int res = 0; Stack stack = new Stack(); for (int i=0; i int pop = stack.pop(); if (stack.isEmpty()) { break; } int width = i - stack.peek() - 1; int h = Math.min(height[i], height[stack.peek()]) - height[pop]; res += width * h; } stack.push(i); } return res; } C++ int trap(vector& height) { int res = 0; stack stack; for (int i=0; i int top = stack.top(); stack.pop(); if (stack.empty()) { break; } int width = i - stack.top() - 1; int h = min(height[i], height[stack.top()]) - height[top]; res += width * h; } stack.push(i); } return res; } 复杂度分析 时间复杂度： O ( n ) O(n) O(n)，每个元素最多入栈一次出栈一次空间复杂度： O ( n ) O(n) O(n)，借助了一个大小为n的栈如果觉得本篇文章对你有所帮助，请帮我点一个免费的赞和关注，这对我非常重要，谢谢！（手动鞠躬） 欢迎关注公众号：程序员冻豆腐，里面有我所有的原创文章 |
【本文地址】