如何在百度做网站,安平做网站的电话,货源网站开发,网站做tips给定 n 个非负整数表示每个宽度为 1 的柱子的高度图#xff0c;计算按此排列的柱子#xff0c;下雨之后能接多少雨水。 输入#xff1a;height [0,1,0,2,1,0,1,3,2,1,2,1]
输出#xff1a;6
解释#xff1a;上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图#xf…给定 n 个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。 输入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 个单位的雨水蓝色部分表示雨水。
输入height [4,2,0,3,2,5]
输出9
自己写的 public class Solution { public int Trap(int[] height) { int[] Theleftnew int[height.Length]; int[] Therightsidenew int[height.Length]; int[] resnew int[height.Length]; int result 0; int leftTheleft[0]; int right Therightside[Therightside.Length - 1]; for (int i 0; i height.Length; i) { if (left height[i]) { Theleft[i] 0; left height[i]; } else { Theleft[i] left - height[i] ; } } for (int i height.Length-1; i 0; i--) { if (right height[i]) { Therightside[i] 0; right height[i]; } else { Therightside[i] right - height[i]; } } for (int i 0; i height.Length; i) { res[i] Math.Min(Theleft[i], Therightside[i]); } for (int i 0; i res.Length; i) { resultresult res[i]; } return result; } } 空间复杂度比较高 和官方的第一个题解一样
方法一动态规划 对于下标 i下雨后水能到达的最大高度等于下标 i 两边的最大高度的最小值下标 i 处能接的雨水量等于下标 i 处的水能到达的最大高度减去 height[i]。
朴素的做法是对于数组 height 中的每个元素分别向左和向右扫描并记录左边和右边的最大高度然后计算每个下标位置能接的雨水量。假设数组 height 的长度为 n该做法需要对每个下标位置使用 O(n) 的时间向两边扫描并得到最大高度因此总时间复杂度是 O(n 2 )。
上述做法的时间复杂度较高是因为需要对每个下标位置都向两边扫描。如果已经知道每个位置两边的最大高度则可以在 O(n) 的时间内得到能接的雨水总量。使用动态规划的方法可以在 O(n) 的时间内预处理得到每个位置两边的最大高度。
创建两个长度为 n 的数组 leftMax 和 rightMax。对于 0≤inleftMax[i] 表示下标 i 及其左边的位置中height 的最大高度rightMax[i] 表示下标 i 及其右边的位置中height 的最大高度。
显然leftMax[0]height[0]rightMax[n−1]height[n−1]。两个数组的其余元素的计算如下
当 1≤i≤n−1 时leftMax[i]max(leftMax[i−1],height[i])
当 0≤i≤n−2 时rightMax[i]max(rightMax[i1],height[i])。
因此可以正向遍历数组 height 得到数组 leftMax 的每个元素值反向遍历数组 height 得到数组 rightMax 的每个元素值。
在得到数组 leftMax 和 rightMax 的每个元素值之后对于 0≤in下标 i 处能接的雨水量等于 min(leftMax[i],rightMax[i])−height[i]。遍历每个下标位置即可得到能接的雨水总量。 但是官方的双指针更优化
方法三双指针 动态规划的做法中需要维护两个数组 leftMax 和 rightMax因此空间复杂度是 O(n)。是否可以将空间复杂度降到 O(1)
注意到下标 i 处能接的雨水量由 leftMax[i] 和 rightMax[i] 中的最小值决定。由于数组 leftMax 是从左往右计算数组 rightMax 是从右往左计算因此可以使用双指针和两个变量代替两个数组。
维护两个指针 left 和 right以及两个变量 leftMax 和 rightMax初始时 left0,rightn−1,leftMax0,rightMax0。指针 left 只会向右移动指针 right 只会向左移动在移动指针的过程中维护两个变量 leftMax 和 rightMax 的值。
当两个指针没有相遇时进行如下操作
使用 height[left] 和 height[right] 的值更新 leftMax 和 rightMax 的值
如果 height[left]height[right]则必有 leftMaxrightMax下标 left 处能接的雨水量等于 leftMax−height[left]将下标 left 处能接的雨水量加到能接的雨水总量然后将 left 加 1即向右移动一位
如果 height[left]≥height[right]则必有 leftMax≥rightMax下标 right 处能接的雨水量等于 rightMax−height[right]将下标 right 处能接的雨水量加到能接的雨水总量然后将 right 减 1即向左移动一位。
当两个指针相遇时即可得到能接的雨水总量。
下面用一个例子 height[0,1,0,2,1,0,1,3,2,1,2,1] 来帮助读者理解双指针的做法。 class Solution {public int trap(int[] height) {int ans 0;int left 0, right height.length - 1;int leftMax 0, rightMax 0;while (left right) {leftMax Math.max(leftMax, height[left]);rightMax Math.max(rightMax, height[right]);if (height[left] height[right]) {ans leftMax - height[left];left;} else {ans rightMax - height[right];--right;}}return ans;}
}
关于动态规划的介绍
动态规划Dynamic Programming简称DP是一种在数学、管理科学、计算机科学、经济学和生物信息学等领域中使用的通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
动态规划经常用于求解具有重叠子问题和最优子结构性质的问题。这里的“重叠子问题”是指在递归算法中反复出现的问题而“最优子结构”是指问题的最优解包含其子问题的最优解。
动态规划的关键步骤 识别子问题将问题分解为小的子问题这些子问题往往是原问题的规模较小的版本。 确定状态定义问题的解状态通常用变量表示例如 dp[i]。 确定状态转移方程找出状态之间的关系即当前状态是如何由之前的一个或多个状态推导出来的。 确定初始状态和边界条件确定状态转移的起点即基本情况或边界条件。 确定求解策略是自底向上从最小的子问题开始解决还是自顶向下递归地解决。 构造最优解根据子问题的解构造原问题的解。
动态规划的常见应用
斐波那契数列计算第n个斐波那契数。背包问题在不超过背包容量的前提下选择物品以最大化价值。最长公共子序列找出两个序列的最长公共子序列。最短路径问题如贝尔曼-福特算法解决带负权边的最短路径问题。矩阵链乘问题计算矩阵乘法的最少操作次数。编辑距离问题计算两个字符串之间的最小编辑距离。
示例斐波那契数列的动态规划解法
斐波那契数列是一个典型的动态规划问题其递归解法存在大量重复计算。动态规划解法如下
状态定义dp[i] 表示斐波那契数列的第 i 个数。状态转移方程dp[i] dp[i-1] dp[i-2]。初始状态dp[0] 0dp[1] 1。循环计算从 2 到 n依次计算 dp[i]。
using System;class Program
{// 动态规划计算斐波那契数列的第n项static long Fibonacci(int n){if (n 1)return n;long[] dp new long[n 1];dp[0] 0;dp[1] 1;for (int i 2; i n; i){dp[i] dp[i - 1] dp[i - 2];}return dp[n];}static void Main(){int n 10; // 计算斐波那契数列的第10项long result Fibonacci(n);Console.WriteLine($Fibonacci of {n} is {result});}
} 动态规划是一种非常强大的方法可以显著提高算法的效率特别是在解决具有重复子问题和最优子结构的问题时。
