做优化网站注意什么,京美建站,购物网站模板代码,wordpress标点出现在行首题目 题解一#xff1a;暴力双重for循环#xff08;以行计算水量#xff09; 1.先找出最高的柱子有多高#xff08;max 3#xff09; 2.然后第一个for为行数#xff08;1#xff0c;2#xff0c;3#xff09; 3.第二个for计算每一行的雨水量#xff08;关键在于去除…题目 题解一暴力双重for循环以行计算水量 1.先找出最高的柱子有多高max 3 2.然后第一个for为行数123 3.第二个for计算每一行的雨水量关键在于去除前面的空白区域利用标志位 boolean iscup true; //标志位若第一次就少于本次最高水位则直接跳过如果是因为处在1 0 1谷底的0就得算水量 4.最后将每一行计算完的雨水量sum总和
//方法一以行计算水量int sum 0;//最终总和int maxdepth max(height);//1-3列for(int i 1;imaxdepth;i){int temp 0;boolean iscup true; //标志位若第一次就少于本次最高水位则直接跳过如果是因为处在1 0 1谷底的0就得算水量//遍历整个数组for(int j0;jheight.length;j){//如果小于当前水位则不更新任何数据 要保证不开始计算水位 才算 if(height[j]iiscup) {continue;}else if(height[j]i!iscup){//根据标志位来判断要不要计算水量temp temp 1;} if(height[j]i){sum sum temp; //把每次累计的temp加到 sumtemp 0;//计算完水量重置tempiscup false;//更新标志位}}}return sum;参考链接解法一按行求
题解二按列求
求每一列的水我们只需要关注当前列以及左边最高的墙右边最高的墙就够了。 装水的多少当然根据木桶效应我们只需要看左边最高的墙和右边最高的墙中较矮的一个就够了。 第一个for循环列数1,2,3,4,5,6,7,8…第二三个for循环分别求出当前列的左边有右边的最大柱子找出两端最矮的然后减去当前列的柱子高度就是当前列的水量 参考链接解法二按列求 int sum 0;//最后的水量//最两端的列不用考虑因为一定不会有水。所以下标从 1 到 length - 2for(int i1; i height.length-1 ; i){//找出左边最高int maxleft 0;for(int j i-1;j0;j--){ //由当前数往前找if(maxleftheight[j]) maxleft height[j];}//找出右边最高int maxright 0;for(int s i1;sheight.length;s){ //由当前数往后找if(maxrightheight[s]) maxright height[s];}//找出两端最矮的int min Math.min(maxleft,maxright);if(min height[i]){sum sum (min - height[i]);//核心就是让两端最小的柱子减去柱子若大于0差值就是当前列的水量}}return sum;题解三动态规划
与上面题解二对比会发现每次对一列去求左右最大的柱子时都会循环一遍左右两边的元素导致会有很多重复操作
可以使用动态规划直接求出每一列的左边或右边的最大柱子
核心 int sum 0;int[] maxleft new int[height.length]; //用于存放i位置的左边的最大柱子int[] maxright new int[height.length];//用于存放i位置的右边的最大柱子//注意边界问题 原则第一个柱子靠左最长柱子默认为0 则i从1开始结束位置为倒数第二个看图好理解for(int i1;iheight.length-1;i){//它后边的墙的右边的最高高度和它后边的墙的高度选一个较大的就是当前列右边最高的墙了。maxleft[i] Math.max(maxleft[i-1],height[i-1]);}for(int j height.length-2;j0;j-- ){//它后边的墙的右边的最高高度和它后边的墙的高度选一个较大的就是当前列右边最高的墙了。maxright[j] Math.max(maxright[j1],height[j1]);}for(int i 1;iheight.length-1;i){int min Math.min(maxleft[i],maxright[i]);if(minheight[i]) sum sum (min -height[i]);}return sum;题解四双指针
动态规划中我们常常可以对空间复杂度进行进一步的优化。
例如这道题中可以看到max_left [ i ] 和 max_right [ i ] 数组中的元素我们其实只用一次然后就再也不会用到了。所以我们可以不用数组只用一个元素就行了。我们先改造下 max_left。
动态图解链接图解接雨水双指针
参考链接解法四双指针 int maxLeft height[0]; int maxRight height[height.length -1];int left 1;int right height.length -2;int sum 0;for(int i 1 ; i height.length -1;i){// while (left right) {//从左开始if(height[left - 1] height[right 1]){maxLeft Math.max(maxLeft,height[left]);if(maxLeft height[left]){sum sum (maxLeft - height[left]);}left;}else {//从右开始maxRight Math.max(maxRight,height[right]);if(maxRight height[right]) {sum sum (maxRight - height[right]);} right--;}}return sum;题解五栈
参考视频单调栈经典来袭LeetCode:42.接雨水
参考链接代码随想录-接雨水 if(height.length2) return 0;int sum 0;StackInteger stack new Stack();int current 0;//先把第一个元素下标加入栈stack.push(0);for(int i1;iheight.length;i){//如果要入栈的元素小于栈顶元素则一直入栈if(!stack.empty()(height[i] height[stack.peek()])) {stack.push(i);}//如果入栈的元素栈顶元素相等可以直接入栈也可以先把栈顶元素出栈再让重复的元素进栈只是重复元素入栈到时候计算面积等于0不影响结果else{while(!stack.empty()height[i] height[stack.peek()]){int mid stack.pop();if(!stack.empty()){int h Math.min(height[stack.peek()],height[i]) - height[mid];int w i - stack.peek() - 1;sum sum (h*w);}}stack.push(i);}}return sum;
