总水量问题
BM94 trapWater()
描述
给定一个整形数组arr，已知其中所有的值都是非负的，将这个数组看作一个柱子高度图，计算按此排列的柱子，下雨之后能接多少雨水。(数组以外的区域高度视为0) 数据范围：数组长度 0 \le n \le 2\times10^50≤n≤2×105，数组中每个值满足 0 < val \le 10^90<val≤109 ，保证返回结果满足 0 \le val \le 10^9 \0≤val≤109 要求：时间复杂度 O(n)O(n)示例1
输入：[3,1,2,5,2,4]返回值：
5说明：
数组 [3,1,2,5,2,4] 表示柱子高度图，在这种情况下，可以接 5个单位的雨水，蓝色的为雨水 ，如题面图。
示例2
输入：[4,5,1,3,2]返回值：
2解答 class Solution{ public class trapWater(int[] heights){ if(height.length<=2)return 0; int result,lMax,rMax=0; int n=height.length; //本质上是双指针的快慢指针方法,通过一个快指针的每一次遍历来实现慢指针所对应的量/面积/体积的准确值; for(int i=1;i<n-1;i++){ // 找右边最高的bar;
for(int j=i;j<n;j++){rMax=Math.max(rMax,height[j]);} // 找左边最高的bar; for(int j=i;j>=0;j--){lMax=Math.max(lMax,height[j]);} result+=Math.min(lMax,rMax)-height[i]; } return result; } } 最大水量问题 BM93 maxArea
描述
给定一个数组height，长度为n，每个数代表坐标轴中的一个点的高度，height[i]是在第i点的高度，请问，从中选2个高度与x轴组成的容器最多能容纳多少水 1.你不能倾斜容器 2.当n小于2时，视为不能形成容器，请返回0 3.数据保证能容纳最多的水不会超过整形范围，即不会超过231-1 数据范围: 0<=height.length<=10^50<=height.length<=1050<=height[i]<=10^40<=height[i]<=104 解法 import java.util.*; public class Solution { public int maxArea(int[] bar) { int n = bar.length; int iL = 0; int iR = n - 1; int result = 0; //本质上是双指针的同向不同步问题,用于解决最值问题; while (iL < iR) { int area = Math.min(bar[iL], bar[iR]) * (iR - iL); result = Math.max(result, area); if (bar[iL] < bar[iR]) iL++;
else iR--; } return result; } } 标签：高度,雨水,height,水量,数组,BM94,trapWater From： https://www.cnblogs.com/somedieyoung/p/16726423.html