华为云建站官网,烟台手机网站建设费用,wordpress怎么注册,中国电子商务研究中心【问题描述】
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图#xff0c;计算按此排列的柱子#xff0c;下雨之后能接多少雨水。上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图在这种情况下可以接 6 个单位的雨水蓝色部分表示雨水。 感谢 Marcos 贡献此图。示例:输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6【解答思路】
1. 栈 -括号匹配 1.当前高度小于等于栈顶高度入栈指针后移。
2.当前高度大于栈顶高度出栈计算出当前墙和栈顶的墙之间水的多少然后计算当前的高度和新栈的高度的关系重复第 2 步。直到当前墙的高度不大于栈顶高度或者栈空然后把当前墙入栈指针后移。
3.水量(Min ( max _ left max _ right ) - height [ i ] ) *两个墙之间的距离 时间复杂度O(N) 空间复杂度O(N)
public int trap6(int[] height) {int sum 0;StackInteger stack new Stack();int current 0;while (current height.length) {//如果栈不空并且当前指向的高度大于栈顶高度就一直循环while (!stack.empty() height[current] height[stack.peek()]) {int h height[stack.peek()]; //取出要出栈的元素stack.pop(); //出栈if (stack.empty()) { // 栈空就出去break; }int distance current - stack.peek() - 1; //两堵墙之前的距离。int min Math.min(height[stack.peek()], height[current]);sum sum distance * (min - h);}stack.push(current); //当前指向的墙入栈current; //指针后移}return sum;
}作者windliang
链接https://leetcode-cn.com/problems/trapping-rain-water/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-8/
2. 按列 暴力
时间复杂度O(N^2) 空间复杂度O(1) 求每一列的水关注当前列以及左边最高的墙右边最高的墙就够了。 装水的多少当然根据木桶效应需要看左边最高的墙和右边最高的墙中较矮的一个就够了 三种情况
较矮的墙的高度大于当前列的墙的高度 左边的墙的高度-减去当前列的高度较矮的墙的高度小于当前列的墙的高度 无水较矮的墙的高度等于当前列的墙的高度 无水
public int trap(int[] height) {int sum 0;//最两端的列不用考虑因为一定不会有水。所以下标从 1 到 length - 2for (int i 1; i height.length - 1; i) {int max_left 0;//找出左边最高for (int j i - 1; j 0; j--) {if (height[j] max_left) {max_left height[j];}}int max_right 0;//找出右边最高for (int j i 1; j height.length; j) {if (height[j] max_right) {max_right height[j];}}//找出两端较小的int min Math.min(max_left, max_right);//只有较小的一段大于当前列的高度才会有水其他情况不会有水if (min height[i]) {sum sum (min - height[i]);}}return sum;
}作者windliang
链接https://leetcode-cn.com/problems/trapping-rain-water/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-8/3. 动态规划
优化 “对于每一列我们求它左边最高的墙和右边最高的墙都是重新遍历一遍所有高度” max_left [i] 代表第 i 列左边最高的墙的高度max_right[i] 代表第 i 列右边最高的墙的高度。
时间复杂度O(N) 空间复杂度O(N)
public int trap(int[] height) {int sum 0;int[] max_left new int[height.length];int[] max_right new int[height.length];for (int i 1; i height.length - 1; i) {max_left[i] Math.max(max_left[i - 1], height[i - 1]);}for (int i height.length - 2; i 0; i--) {max_right[i] Math.max(max_right[i 1], height[i 1]);}for (int i 1; i height.length - 1; i) {int min Math.min(max_left[i], max_right[i]);if (min height[i]) {sum sum (min - height[i]);}}return sum;
}作者windliang
链接https://leetcode-cn.com/problems/trapping-rain-water/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-8/优化 左右数组-左数组
public int trap(int[] height) {int sum 0;int max_left 0;int[] max_right new int[height.length];for (int i height.length - 2; i 0; i--) {max_right[i] Math.max(max_right[i 1], height[i 1]);}for (int i 1; i height.length - 1; i) {max_left Math.max(max_left, height[i - 1]);int min Math.min(max_left, max_right[i]);if (min height[i]) {sum sum (min - height[i]);}}return sum;
}作者windliang
链接https://leetcode-cn.com/problems/trapping-rain-water/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-8/
4. 动态规划 双指针优化
因为第一个柱子和最后一个柱子肯定不能装水因为不作为装水柱子而是作为左边最高柱子和右边最高柱子 时间复杂度O(N) 空间复杂度O(1)
使用双指针左右两边各一个指针 我们使用一根一根柱子计算装水量的方法left 表示左边当前遍历的柱子即左边我们需要计算能够装多少水的柱子left_max 表示 left 的左边最高的柱子长度不包括 leftright 表示右边当前遍历的柱子right_max 表示 right 的右边最高的柱子长度不包括 right我们有以下几个公式 当 left_max right_max 的话那么我们就判断 left_max 是否比 left 高因为根据木桶效应一个桶装水量取决于最短的那个木板这里也一样柱子能否装水取决于左右两边的是否都存在比它高的柱子因为 left_max right_max 了那么我们只需要比较 left_max 即可如果 left_max left那么装水量就是 left_max - left如果 left_max left那么装水量为 0即 left 装不了水当 left_max right_max 的话同理如上比较 right_max 和 right 为什么 right_max 和 left 隔这么远我们还可以使用 right_max 来判断前提left_max right_maxright_max 虽然跟 left 离得远但有如下两种情况1、left 柱子和 right_max 柱子之间没有比 right_max 柱子更高的柱子了那么情况如下 left 能否装水取决于 left_max 柱子是否比 left 高|| || | |↑ ↑ ↑l_m l r_m2、left 柱子和 right_max 柱子之间存在比 right_max 柱子更高的柱子那么情况如下因为存在了比 right_max 更高的柱子那么我们仍然只需要判断 left_max 是否比 left 高因为右边已经存在比 left 高的柱子|| || | || | | |↑ ↑ ↑ ↑l_m l mid r_m初始化指针left 1;right len - 2;left_max 0;right_max len - 1;因为第一个柱子和最后一个柱子肯定不能装水因为不作为装水柱子而是作为左边最高柱子和右边最高柱子public int trap(int[] height) {int sum 0;int max_left 0;int max_right 0;int left 1;int right height.length - 2; // 加右指针进去for (int i 1; i height.length - 1; i) {//从左到右更if (height[left - 1] height[right 1]) {max_left Math.max(max_left, height[left - 1]);int min max_left;if (min height[left]) {sum sum (min - height[left]);}left;//从右到左更} else {max_right Math.max(max_right, height[right 1]);int min max_right;if (min height[right]) {sum sum (min - height[right]);}right--;}}return sum;
}作者windliang
链接https://leetcode-cn.com/problems/trapping-rain-water/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-8/5. 逐行分析 超时
时间复杂度O(N^2) 空间复杂度O(1)
public int trap(int[] height) {int sum 0;int max getMax(height);//找到最大的高度以便遍历。for (int i 1; i max; i) {boolean isStart false; //标记是否开始更新 tempint temp_sum 0;for (int j 0; j height.length; j) {if (isStart height[j] i) {temp_sum;}if (height[j] i) {sum sum temp_sum;temp_sum 0;isStart true;}}}return sum;
}
private int getMax(int[] height) {int max 0;for (int i 0; i height.length; i) {if (height[i] max) {max height[i];}}return max;
}作者windliang
链接https://leetcode-cn.com/problems/trapping-rain-water/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-8/
【总结】
动态规划空间换时间双指针是个好工具 -链表题目也可以使用
2.栈-类比括号匹配
当是数组入栈时入栈下标数组的值可以通过下标获得
横纵思考 多思考几步 想清楚所有情况再动手
