一、IDEA注释显示图片
在做题时,需要对照这图片,才能更好的梳理思路。
首先,注释里添加<img/>
标签
之后,将鼠标光标放置在需要以阅读模式预览注释的地方,然后按快捷键Ctrl+Alt+Q
即可
二、接雨水算法
先看接雨水算法的具体描述
2.1 暴力解法
我做的时候,就对着这个柱状图一直发呆,然后大概发现了思路。
我采取的是分而治之,也就是说,我依次遍历x轴,计算x所在的积水量。积水量=Min(leftMax,rightMax)-height[i]
- leftMax: 表示
x<i
的height的最大值 - rightMax: 表示
x>i
的height的最大值
思路有了,上代码。
class Solution {public int trap(int[] height) {int n = 0;for (int i = 0; i < height.length; i++) {int max = getMax(height, i);int i1 = height[i];if (max > i1) {n += max - i1;}}return n;}/*** 获取i位置的左右两侧的最大值,取出最大值中的最小值*/public int getMax(int[] height, int i) {if (i <= 0 || i >= height.length - 1) {return 0;}int leftMax = -1, rightMax = -1;//获取左边最大值for (int j = i - 1; j >= 0; j--) {int i1 = height[j];if (i1 > leftMax) {leftMax = i1;}}//获取右边最大值for (int j = i + 1; j < height.length; j++) {int i1 = height[j];if (i1 > rightMax) {rightMax = i1;}}return Math.min(leftMax, rightMax);}
}
2.2 优化解法
这个做法的时间复杂度是O(n²),导致后面就超时了。慢就慢在,获取每个下标i最大值时,都需要去循环比较获取。能不能提前将最大值计算出来呢?其实可行的
这里面其实是有规律的,以数组[4,2,0,3,2,5]为例,其对应的每个下标的leftMax和rightMax,如下图。
直接上代码,看代码理解。
class Solution {public int trap(int[] height) {int n = 0;//求出每个位置的左侧最大值int[] leftMax = new int[height.length];for (int i = 0; i < height.length; i++) {if (i == 0) {leftMax[i] = 0;} else {leftMax[i] = Math.max(leftMax[i - 1], height[i - 1]);}}//求出每个位置的右侧最大值int[] rightMax = new int[height.length];for (int i = height.length - 1; i >= 0; i--) {if (i == height.length - 1) {rightMax[i] = 0;} else {rightMax[i] = Math.max(rightMax[i + 1], height[i + 1]);}}//每个位置的左右两侧短板值与当前位置值的差,即当前位置的积水for (int i = 0; i < height.length; i++) {int min = Math.min(leftMax[i], rightMax[i]);int i1 = height[i];if (min > i1) {n += min - i1;}}return n;}
}
时间复杂度为O(n),太妙了。