LeetCode——42. 接雨水(Java)
2021/11/3 11:10:24
本文主要是介绍LeetCode——42. 接雨水(Java),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目描述
题干: 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 示例 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 个单位的雨水(蓝色部分表示雨水)。 示例 2: 输入:height = [4,2,0,3,2,5] 输出:9
题目描述
返回能接到的雨水格子数,官方题解给出了很多种方法,说几个可以理解的方法 任何问题离不开暴力解答,但是这道题的暴力思想我估计都不好想 你需要知道如何计算节水数量的方式,就是当前元素到左右最高边界中较小的差然后求和 所以我们需要先计算出每个元素盛水的左右边界值,这里就有两种方式 暴力的话就需要每次计算左右边界,如果采用动态规划的思想,可以想把边界值存储起来 这就是两种方法,再其次就是采用单调递减栈的方式,因为只要高度是递减的 那当它一旦遇到递增的就可以接水,利用这个思路,我们可以使用递减栈的思想来计算 最后还有一种双指针的方式,因为时间有限就没有理解,大家可以去官方题解查看解析或者视频
正确代码
// 暴力 public int trap(int[] height) { int ans = 0; int size = height.length; for (int i = 1; i < size - 1; i++) { int max_left = 0, max_right = 0; for (int j = i; j >= 0; j--) { max_left = Math.max(max_left, height[j]); } for (int j = i; j < size; j++) { max_right = Math.max(max_right, height[j]); } ans += Math.min(max_left, max_right) - height[i]; } return ans; } // 动态规划 public int trap01(int[] height) { if (height == null || height.length == 0) { return 0; } int ans = 0, size = height.length; int[] left_max = new int[size]; int[] right_max = new int[size]; left_max[0] = height[0]; for (int i = 1; i < size; i++) { left_max[i] = Math.max(height[i], left_max[i - 1]); } right_max[size - 1] = height[size - 1]; for (int i = size - 2; i >= 0; i--) { right_max[i] = Math.max(height[i], right_max[i + 1]); } for (int i = 1; i < size - 1; i++) { ans += Math.min(left_max[i], right_max[i]) - height[i]; } return ans; } // 单调递减栈 public int trap02(int[] height) { int ans = 0, current = 0; Deque<Integer> stack = new LinkedList<>(); while (current < height.length) { while (!stack.isEmpty() && height[current] > height[stack.peek()]) { int top = stack.pop(); if (stack.isEmpty()) break; int distance = current - stack.peek() - 1; int bounded_height = Math.min(height[current], height[stack.peek()]) - height[top]; ans += distance * bounded_height; } stack.push(current++); } return ans; } // 双指针 public int trap03(int[] height) { int left = 0, right = height.length - 1; int ans = 0; int left_max = 0, right_max = 0; while (left < right) { if (height[left] < height[right]) { if (height[left] >= left_max) { left_max = height[left]; } else { ans += (left_max - height[left]); } ++left; } else { if (height[right] >= right_max) { right_max = height[right]; } else { ans += (right_max - height[right]); } --right; } } return ans; }
总结
上次说到单调递减栈可以用来统计元素后面比自己大的元素,在这里也同样好用 还有双指针的思想,绝对是将复杂度降低的绝妙方式,我个人就很喜欢这个思想 如果文章存在问题或者有更好的题解,欢迎在评论区斧正和评论,各自努力,最高处见
这篇关于LeetCode——42. 接雨水(Java)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-30PS网页切图项目实战:初学者必备指南
- 2024-09-30Span标签项目实战:新手入门教程
- 2024-09-309D资料入门指南:轻松掌握基础操作
- 2024-09-30如何获取和利用变形资料:新手入门指南
- 2024-09-30弹性盒子布局资料:新手必读教程
- 2024-09-30手把手教你如何使用“点击加载资料”功能
- 2024-09-30封装资料入门教程:轻松掌握封装资料的方法与技巧
- 2024-09-30钢琴效果资料:新手入门指南
- 2024-09-30滚动吸顶资料详解:轻松掌握网页常见布局技巧
- 2024-09-30后台交互资料详解:新手入门教程