给定n个非负整数表示每个宽度为1的柱子的高度题,计算按此排列的柱子,下雨之后能接多少雨水。
"""" 特殊的单调递增 序列a按照最高值划分为两个数组b、c,后半部分翻转 对每一个数组,遍历数组, 若当前最大值t_max小于x,则更新t_max = x; 若大于,则计数 t_max - x """ def count(a): ret, t_max = 0, 0 for x in a: if x > t_max: t_max = x else: ret += t_max - x return ret if __name__ == "__main__": a = list(map(int, input().strip().split(','))) b = a[a.index(max(a)):][::-1] c = a[:a.index(max(a)) + 1] ans = 0 ans += count(b) ans += count(c) print(ans)
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack; public class Solution18_计算题_接雨水 { /** * LeetCode 42题 接雨水 难度 Hard * 此题提供四种解法供参考,由于牛客网的测试数据过大,结果会出现溢出,用 long 保存结果 * 有两个方法没有AC过的。 * 但是能提供不错的思路。 */ public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); String[] strs = bf.readLine().split(","); int[] nums = new int[strs.length]; for (int i = 0; i < strs.length; i++) { nums[i] = Integer.parseInt(strs[i]); } System.out.println(getWater3(nums)); } /** * 方法一:暴力法 最容易联想到的办法 复杂度过高不能过 * 计算每个位置可以接的水 * height[i] 找出height[i]左边的最大值,和右边的最大值 * 取其中的较小者减去height[i] 就是当前位置可以接到的水的量 * 时间复杂度为 O(n^2) * 空间复杂度为 O(1) */ private static long getWater1(int[] height) { if (height.length < 3) return 0; int n = height.length; long sum = 0; for (int i = 1; i < n - 1; i++) {//第一个位置和最最后一个位置肯定是不能接水的 int left_max = 0, right_max = 0;//记录左边和右边的最大值 for (int j = i - 1; j >= 0; j--) left_max = Math.max(left_max, height[j]); for (int j = i + 1; j < n; j++) right_max = Math.max(right_max, height[j]); int a = Math.min(left_max, right_max) - height[i]; sum += a > 0 ? a : 0; } return sum; } /** * 方法二:牛客网能过 * 暴力法每次都要去查找左边和右边的最大值 * 我们不妨直接先把该值存储起来 * 时间复杂度为 O(n) * 空间复杂度为 O(n) */ public static long getWater(int[] height) { if (height.length < 2) return 0; int n = height.length; int[] left_max = new int[n]; int[] right_max = new int[n]; left_max[0] = height[0]; right_max[n - 1] = height[n - 1]; for (int i = 1; i < n; i++) { left_max[i] = Math.max(height[i], left_max[i - 1]); right_max[n - i - 1] = Math.max(height[n-i-1], right_max[n-i]); } long ans = 0; for (int i = 1; i < n - 1; i++) { ans += Math.min(left_max[i], right_max[i]) - height[i]; } return ans; } /** * 方法三:借助栈 时间过久 没有通过 * 如果不是很理解出栈过程,可以画画图便于理解。 */ private static long getWater3(int[] height) { long sum = 0; Stack<Integer> stack = new Stack<>(); int p = 0; while (p < height.length) { //如果栈不为空并且当前指向的高度比栈顶的元素还大 while (!stack.isEmpty() && height[p] > height[stack.peek()]) { //取出栈顶元素 int h = height[stack.pop()]; if (stack.isEmpty()) { break; } int dc = p - stack.peek() - 1;//两墙之间的距离 int min = Math.min(height[stack.peek()], height[p]) - height[h]; sum += dc * min; } stack.add(p++); } return sum; } /** * 方法四:通过 * 双指针 在一遍遍历中记录左边和右边的最大值 */ private static long getWater4(int[] height) { int max_left = 0, max_right = 0; long sum = 0; int point_left = 1, point_right = height.length - 2; for (int i = 1; i < height.length - 1; i++) { //从左往右更新 if (height[point_left - 1] < height[point_right + 1]) { max_left = Math.max(max_left, height[point_left - 1]); int min = max_left - height[point_left]; sum += min > 0 ? min : 0; point_left++; } else { max_right = Math.max(max_right, height[point_right + 1]); int min = max_right - height[point_right]; sum += min > 0 ? min : 0; point_right--; } } return sum; } }
var str = readline(); var arr=str.split(','); var num=trap(arr); console.log(num) function trap (height) { let left = 0, right = height.length - 1 let count = 0 let leftMax = 0, rightMax = 0 while (left <= right) { leftMax = Math.max(leftMax, height[left]) rightMax = Math.max(rightMax, height[right]) if (leftMax < rightMax) { count += leftMax - height[left] left++ } else { count += rightMax - height[right] right-- } } return count };
#include <bits/stdc++.h> using namespace std; int main() { vector<int> a; string s; cin >> s; int cur=0, sign = 1; for (int i = 0; i < s.length(); i++) { if (!isdigit(s[i])) { a.push_back(cur * sign); cur = 0; sign = 1; } else cur = cur * 10 + s[i] - '0'; } a.push_back(cur * sign); int n = a.size(); // left[i]表示i左边的最大值,right[i]表示i右边的最大值 vector<int> left(n), right(n); left[0]=0; right[n-1]=0; for (int i = 1; i < n; i++) left[i] = max(left[i - 1], a[i - 1]); for (int i = n - 2; i >= 0; i--) right[i] = max(right[i + 1], a[i + 1]); int water = 0; for (int i = 0; i < n; i++) { int level = min(left[i], right[i]); water += max(0, level - a[i]); } cout<< water; return 0; }不知道什么原因,哪位大神指导一下不通过您的代码已保存 答案错误:您提交的程序没有通过所有的测试用例 case通过率为86.67%
#include<bits/stdc++.h> using namespace std; int main() { string s; cin>>s; s+=','; istringstream ss(s); int temp,Max=INT_MIN,index; char c; vector<int>v; int i = 0; while(ss>>temp>>c) { v.push_back(temp); // 找到最高的柱子 以其为界 划分为左右两个容器 if(temp>Max) { Max = temp; index = i; } i++; } int left_max = 0,right_max = 0; long sum = 0; int volume; if(v[0]>left_max) left_max = v[0]; // 左边容器接水量 for(int j = 1;j<index;j++) { // 当前位置接水量为 min(容器左边界,容器右边界)-当前位置的柱高 volume = left_max-v[j]; if(volume>0) sum+=volume; // 更新容器边界 if(v[j]>left_max) left_max = v[j]; } if(v[v.size()-1]>right_max) right_max = v[v.size()-1]; // 右边容器接水量 for(int k=v.size()-2;k>index;k--) { volume = right_max-v[k]; if(volume>0) sum+=volume; if(v[k]>right_max) right_max = v[k]; } cout<<sum<<endl; return 0; }
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #define forward(from,to) for(int i=from;i<to;++i) #define back(from,to) for(int i=from;i>to;--i) int d[1000001]; int main() { int count = 0; int maxValue = 0; int maxIndex = 0; while (scanf("%d", &d[count])) { if (d[count] > maxValue) { maxValue = d[count]; maxIndex = count; } ++count; if (getchar() == '\n')break; } long long answer = 0; int cvalue = 0; forward(0, maxIndex) { if (cvalue < d[i])cvalue = d[i]; else answer += cvalue - d[i]; } cvalue = 0; back(count - 1, maxIndex) { if (cvalue < d[i])cvalue = d[i]; else answer += cvalue - d[i]; } printf("%lld\n", answer); return 0; }
import java.util.Scanner; public class Main { // 思路:先将字符串分割,从前往后,选择第一个板作为参照,直到找到第二块比它高或者和它一样高的板在计算盛水量, // 记得计算损失量,将第二块板作为下一次的起始板,继续遍历;然后从后往前进行相同的遍历。 public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String line = scanner.nextLine(); String[] split = line.split(","); int[] arr = new int[split.length]; for (int i = 0; i < split.length; i++) { arr[i] = Integer.parseInt(split[i]); } System.out.println(receiveRainwater(arr)); } public static long receiveRainwater(int[] arr) { if (arr.length == 0) { return 0; } long amount = 0; int start = 0; while (true) { int index = start + 1; if (index == arr.length) { break; } long deBuff = 0; while (index < arr.length) { if (arr[start] <= arr[index]) { break; } deBuff += arr[index]; index++; } if (index == arr.length) { break; } amount += (long) (index - start - 1) * (arr[start] > arr[index] ? arr[index] : arr[start]) - deBuff; start = index; } int end = start - 1; start = arr.length - 1; while (true) { int index = start - 1; if (index == end) { break; } long deBuff = 0; while (index > end) { if (arr[start] <= arr[index]) { break; } deBuff += arr[index]; index--; } if (index == end) { break; } amount += (long) (start - index - 1) * (arr[start] > arr[index] ? arr[index] : arr[start]) - deBuff; start = index; } return amount; } }
import java.io.InputStreamReader; import java.io.BufferedReader; import java.io.IOException; public class Main { // 思路:先将字符串分割,从前往后,选择第一个板作为参照,直到找到第二块比它高或者和它一样高的板在计算盛水量, // 记得计算损失量,将第二块板作为下一次的起始板,继续遍历;然后从后往前进行相同的遍历。 public static void main(String[] args) { BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in)); // bufferedraader+inputstream 更快 String line = null; try { line = bufferedReader.readLine(); } catch (IOException e) { e.printStackTrace(); } String[] split = line.split(","); int[] arr = new int[split.length]; for (int i = 0; i < split.length; i++) { arr[i] = Integer.parseInt(split[i]); } System.out.println(receiveRainwater(arr)); } public static long receiveRainwater(int[] arr) { if (arr.length == 0) { return 0; } long amount = 0; int start = 0; while (true) { int index = start + 1; if (index == arr.length) { break; } long deBuff = 0; while (index < arr.length) { if (arr[start] <= arr[index]) { break; } deBuff += arr[index]; index++; } if (index == arr.length) { break; } amount += (long) (index - start - 1) * (arr[start] > arr[index] ? arr[index] : arr[start]) - deBuff; start = index; } int end = start - 1; start = arr.length - 1; while (true) { int index = start - 1; if (index == end) { break; } long deBuff = 0; while (index > end) { if (arr[start] <= arr[index]) { break; } deBuff += arr[index]; index--; } if (index == end) { break; } amount += (long) (start - index - 1) * (arr[start] > arr[index] ? arr[index] : arr[start]) - deBuff; start = index; } return amount; } }
def main(): H = list(map(int, input().split(','))) n = len(H) if n < 3: return 0 Q = 0 peak = max(H) p = [0,0] for j in range(2): H.reverse() p[j] = H.index(peak) for i in range(1,p[j]): if H[i] < H[i-1]: Q += H[i-1] - H[i] H [i] = H[i-1] if p[0] + p[1] != n - 1: Q += (n-p[0]-p[1]-2) * peak - sum(H[p[1]+1: -p[0]-1]) return Q if __name__ == '__main__': print(main())
l=[int(i) for i in input().split(',')] i=0 ;j=len(l)-1 lh=l[0] ;rh=l[-1] s=0 while i<j: if l[i]<=l[j]: i+=1 if l[i]<=lh:s+=lh-l[i] else:lh=l[i] else: j-=1 if l[j]<=rh:s+=rh-l[j] else:rh=l[j] print(s)
function cal_rain(arr) { if (arr.length === 0) { return 0; } let left = arr[0]; let tmpArr = []; let rain = 0; for (let i = 1; i < arr.length; i++) { if (arr[i] >= left) { //开始计算雨水量 tmpArr.forEach(item => { rain += left - item; }); left = arr[i]; tmpArr = []; } else { tmpArr.push(arr[i]); } } //剩余部分 let high = tmpArr[0]; let highIndex = 0; tmpArr.forEach((item, index) => { if (item >= high) { high = item; highIndex = index; } }); for (let i = 0; i < highIndex; i++) { rain += high - tmpArr[i]; } return rain; }
#include <bits/stdc++.h> (755)#define UF(i,start,end) for(int i=start;i<end;i++) #define DF(i,start,end) for(int i=start;i>=end;i--) //freopen("temp.in","r",stdin); using namespace std; /* 找先降后升的序列 //两个栈,一个从左到右,一个从右到左都维护递增序列,会在最高处碰头 //如果两个递增的点的位置相差超过1,则可以计算其接水度 */ //全部相加可能溢出 int main(){ string s; cin>>s; vector<int> V; int start=0,index; while((index=s.find(",",start))!=string::npos){ V.push_back(atoi(s.substr(start,index-start+1).c_str())); start = index+1; } V.push_back(atoi(s.substr(start).c_str())); stack<int> S,T; int n = V.size(); for(int i=0;i<n;i++){ if(S.empty()) S.push(i); else if(V[i]>=V[S.top()]){ S.push(i); } } int m = 0;//从右往左找时的边界 左边已经找到这了 if(!S.empty()) m = S.top(); for(int i=n-1;i>=m;i--){ if(T.empty()) T.push(i); else if(V[i]>=V[T.top()]){ T.push(i); } } long long ans = 0; while(T.size()>=2){ int l = T.top(); T.pop(); if(l==T.top()-1) continue; for(int i=T.top()-1;i>l;i--){ ans+=V[T.top()]-V[i]; } } while(S.size()>=2){ int r = S.top(); S.pop(); if(r==S.top()+1) continue; for(int i=S.top()+1;i<r;i++){ ans+=V[S.top()]-V[i]; } } cout<<ans<<endl; return 0; }
heights=list(map(int,input().strip().split(','))) size=len(heights) waters=[0]*size val=heights[0] for i in range(1,size): if val>heights[i]: waters[i]=val-heights[i] else: val=heights[i] waters[-1]=0 val=heights[-1] for i in range(size-2,-1,-1): if val>heights[i]: waters[i]=min(waters[i],val-heights[i]) else: val=heights[i] waters[i]=0 print(sum(waters))
arrs = list(map(int, input().split(','))) max_left,max_right = [],[] temp_left,temp_right=0,0 for i in range(len(arrs)): max_left.append(temp_left) if arrs[i]>temp_left: temp_left = arrs[i] for i in range(len(arrs)-1,-1,-1): max_right.append(temp_right) if arrs[i]>temp_right: temp_right = arrs[i] res = 0 for i in range(len(arrs)): curr = min(max_right[len(arrs)-i-1],max_left[i])-arrs[i] if curr>0: res+=curr print(res)
import java.util.Scanner; public class Main{ public static void main(String[] args) { @SuppressWarnings("resource") Scanner sc = new Scanner(System.in); String[] a = sc.nextLine().split(","); int[] m = new int[a.length]; for(int i=0; i<a.length; i++) { m[i] = Integer.parseInt(a[i]); } int s = getSpace(m); System.out.println(s); } private static int getSpace(int[] m) { //遍历最高的柱子,获取最大高度和下标 int max = 0; int max_index = 0; for(int i=0; i<m.length; i++) { if(m[i] > max) { max = m[i]; max_index = i; } } // 从最左端遍历到max_index,计算左边的雨水面积(高度下降时计算水位) int sum = 0; int cur = 0; int l, r; for(l=0; l<max_index; l++) { if(cur < m[l]) cur = m[l]; else sum += (cur - m[l]); } // 从最右端遍历到max_index,计算右边的雨水面积(高度下降时计算水位) for(r=m.length-1,cur=m[m.length-1]; r>max_index; r--) { if(cur < m[r]) cur = m[r]; else sum += (cur - m[r]); } return sum; } }