给定一个数组arr,已知其中所有的值都是非负的,将这个数组看作一个容器, 请返回容器能装多少水比如,arr = {3,1,2,5,2,4},根据值画出的直方图就是容器形状,该容 器可以装下5格水再比如,arr = {4,5,1,3,2},该容器可以装下2格水。
这题的整体解题思路是:数组中的任意一个数X,计算出X左侧数组中的最大值记为 leftMax,X右侧数组中的最大值记为 rightMax。根据公式 Math.max(Math.min(leftMax,rightMax)- X,0) 可以计算出数组中每个位置可以装下水的水量,全部相加即为最终答案。
本题在计算X左右两侧数组中的最大值时,可以进行不断的优化。
优化一:在X位置的左右两侧每次分别使用for循环查找两侧的最大值。本题的时间复杂度为:O(N^2)。
- public static int water1(int[] arr){
- if (arr==null || arr.length<2){
- return 0;
- }
- int N = arr.length;
- int water = 0;
- for (int i = 1;i
1;i++){ - int leftMax = Integer.MIN_VALUE;
- for (int j = 0;j
- leftMax = Math.max(leftMax,arr[j]);
- }
- int rightMax = Integer.MIN_VALUE;
- for (int j = i+1;j
- rightMax = Math.max(rightMax,arr[j]);
- }
- water += Math.max(Math.min(leftMax,rightMax)-arr[i],0);
- }
- return water;
- }
优化二:使用预处理数组,提前计算出X位置左侧与右侧最大值记录在数组中。在遍历过程中直接查找预处理数组中提前计算的最大值。本题的时间复杂度由原来的O(N^2)降为O(N)。
- public static int water2(int[] arr){
- if (arr == null || arr.length < 2){
- return 0;
- }
- int N = arr.length;
- int[] leftMax = new int[N];
- leftMax[0] = arr[0];
- for (int i =1;i
- leftMax[i] = Math.max(leftMax[i-1],arr[i]);
- }
- int[] rightMax = new int[N];
- rightMax[N-1] = arr[N-1];
- for (int i = N-2;i>=0;i--){
- rightMax[i] = Math.max(rightMax[i+1],arr[i]);
- }
- int water = 0;
- for (int i = 1;i
1;i++){ - water += Math.max(Math.min(leftMax[i-1],rightMax[i+1])-arr[i],0);
- }
- return water;
- }
优化三:仍然使用预处理数组,但是我们只是用一个预处理数组用于记录右侧数组的最大值,这是因为我们数组在从左遍历的过程中我们可以使用一个变量通过不断更新的方式来记录左侧数组的最大值,这样就节省了一个数组。
- public static int water3(int[] arr){
- if (arr == null ||arr.length<2){
- return 0;
- }
- int N = arr.length;
- int[] rightMaxs = new int[N];
- rightMaxs[N-1] = arr[N-1];
- for (int i =N-2;i>=0;i--){
- rightMaxs[i] = Math.max(rightMaxs[i+1],arr[i]);
- }
- int water = 0;
- int leftMax = arr[0];
- for (int i = 1;i
1;i++){ - water += Math.max(Math.min(leftMax,rightMaxs[i+1])-arr[i],0);
- leftMax = Math.max(leftMax,arr[i]);
- }
- return water;
- }
优化四: 不使用预处理数组,我们采用双指针的方式。数组的头和尾不可能形成容器直接跳过,记录一个左边最大值,一个右边最大值,如果左小于右先结算左边水量,如果右小于左先结算右边的水量,哪边是瓶颈就先结算哪边的水量。
- public static int water4(int[] arr){
- if (arr == null ||arr.length<2){
- return 0;
- }
- int N = arr.length;
- int L = 1;
- int leftMax = arr[0];
- int R = N-2;
- int rightMax = arr[N-1];
- int water = 0;
- while (L<=R){
- if (leftMax <= rightMax){
- water += Math.max(0,leftMax-arr[L]);
- leftMax = Math.max(leftMax,arr[L++]);
- }else {
- water += Math.max(0,rightMax-arr[R]);
- rightMax = Math.max(rightMax,arr[R--]);
- }
- }
- return water;
- }
问题描述二:
如果给你一个二维数组,每一个值表示这一块地形的高度,求整块地形能装下多少水。
思路
利用小根堆求解。由于四个边都不能形成装水区域,首先把四个边加入到小根堆中,在准备一个布尔类型的二维数组,记录所有进过小根堆的位置,进过一次后就不允许在进入小根堆了。准备一个变量max用于记录所在湖的最大高度。此时第一次弹出的一定是边界上最小的位置,以此位置为根据地,把根据地的高度记录在max中,把它四周未加入过小根堆的点加入小根堆,查找周边是否有比它地势低的点,就可以计算出地势低点的水位高度。每次弹出一个元素,查看当前元素的值是否比之前的最大值还大,若成立则更新最大值,然后收集他相邻的上下左右四个位置的水位,然后把四个位置放入小根堆,重复上述过程直到小根堆变为空。
代码
- public static class Node {
- public int value;
- public int row;
- public int col;
-
- public Node(int v, int r, int c) {
- value = v;
- row = r;
- col = c;
- }
- }
-
- public static class NodeComparator implements Comparator
{ -
- @Override
- public int compare(Node o1, Node o2) {
- return o1.value - o2.value;
- }
- }
-
- public static int trapRainWater(int[][] heightMap) {
- if (heightMap == null || heightMap.length == 0 || heightMap[0] == null || heightMap[0].length == 0) {
- return 0;
- }
- int N = heightMap.length;
- int M = heightMap[0].length;
- boolean[][] isEnter = new boolean[N][M];
- PriorityQueue
heap = new PriorityQueue<>(new NodeComparator()); -
- for (int col = 0; col < M - 1; col++) {
- isEnter[0][col] = true;
- heap.add(new Node(heightMap[0][col], 0, col));
- }
- for (int row = 0; row < N - 1; row++) {
- isEnter[row][M - 1] = true;
- heap.add(new Node(heightMap[row][M - 1], row, M - 1));
- }
- for (int col = M - 1; col > 0; col--) {
- isEnter[N - 1][col] = true;
- heap.add(new Node(heightMap[N - 1][col], N - 1, col));
- }
- for (int row = N - 1; row > 0; row--) {
- isEnter[row][0] = true;
- heap.add(new Node(heightMap[row][0], row, 0));
- }
-
- int water = 0;
- int max = 0;//每次node在弹出的时候,如果value更大,更新max,否则max的值维持不变
- while (!heap.isEmpty()) {
- Node cur = heap.poll();
- max = Math.max(max, cur.value);
- int r = cur.row;
- int c = cur.col;
- if (r > 0 && !isEnter[r - 1][c]) {
- water += Math.max(0, max - heightMap[r - 1][c]);
- isEnter[r - 1][c] = true;
- heap.add(new Node(heightMap[r - 1][c], r - 1, c));
- }
- if (r < N - 1 && !isEnter[r + 1][c]) {
- water += Math.max(0, max - heightMap[r + 1][c]);
- isEnter[r + 1][c] = true;
- heap.add(new Node(heightMap[r + 1][c], r + 1, c));
- }
- if (c > 0 && !isEnter[r][c - 1]) {
- water += Math.max(0, max - heightMap[r][c - 1]);
- isEnter[r][c - 1] = true;
- heap.add(new Node(heightMap[r][c - 1], r, c - 1));
- }
- if (c < M - 1 && !isEnter[r][c + 1]) {
- water += Math.max(0, max - heightMap[r][c + 1]);
- isEnter[r][c + 1] = true;
- heap.add(new Node(heightMap[r][c + 1], r, c + 1));
- }
- }
- return water;
- }
时间复杂度
遍历二维数组中的全部数字需要时间复杂度为:O(N*M)
小根堆的时间复杂度为O(logk),其中k最大为N*M。
综上所述,该题的时间复杂度为:O(N*M*log(N*M))
-
相关阅读:
kotlin coroutine源码解析之Job启动流程
java计算机毕业设计环巢湖区域旅游网站MyBatis+系统+LW文档+源码+调试部署
OKR,为什么我喜欢他们
详解linux多线程——互斥锁、条件变量、读写锁、自旋锁、信号量
把请求头信息添加到请求报文中,然后发送请求到淘宝,显示回复信息
7.2 通过API创建新进程
使用 HTTP Client 轻松进行 API 测试
2.6一个小工具的使用snipaste
机器人课程教师面对的困境有哪些(补充)
nacos服务注册源码过程阅读
-
原文地址:https://blog.csdn.net/z1171127310/article/details/127704037
-
最新文章
-
C++11 线程同步接口std::condition_variable和std::future的简单使用
Go runtime 调度器精讲(十一):总览全局
Spring框架漏洞总结
Angular 18+ 高级教程 – 国际化 Internationalization i18n
基于Tauri2+Vue3搭建桌面端程序|tauri2+vite5多窗口|消息提醒|托盘闪烁
ComfyUI 基础教程(五) —— 应用 IP-Adapter 实现图像风格迁移
网络空间的“边水往事”?针对华语黑产及用户进行攻击的 APT-K-UN3 活动分析
伪装“黑神话悟空修改器”传播木马的活动分析
全球蓝屏后,微软决定将安全踢出Windows内核
Java读取寄存器数据的方法