给定一个整形数组arr,已知其中所有的值都是非负的,将这个数组看作一个容器,请返回容器能装多少水。
具体请参考样例解释
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); String[] strArr = br.readLine().split(" "); int[] heights = new int[n]; for(int i = 0; i < n; i++) heights[i] = Integer.parseInt(strArr[i]); int leftMax = heights[0], rightMax = heights[n - 1]; int left = 0, right = n - 1; long volumn = 0; while(left < right){ leftMax = Math.max(leftMax, heights[left]); rightMax = Math.max(rightMax, heights[right]); if(leftMax < rightMax){ volumn += leftMax - heights[left]; left ++; }else{ volumn += rightMax - heights[right]; right --; } } System.out.println(volumn); } }
#include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; if(n<=0) return 0; int a[n]; for(int i=0;i<n;i++) cin>>a[i]; int i=0, j=n-1, l=a[0], r=a[n-1]; long s=0; while(i<j){ if(l>r){ j--; if(a[j]>r) r = a[j]; else s += (r-a[j]); }else{ i++; if(a[i]>l) l = a[i]; else s += (l-a[i]); } } cout<<s<<endl; return 0; }
//单调栈 int main(){ int size; cin >> size; vector<int> array(size); for(int i = 0; i < size; i++) cin >> array[i]; stack<int> max_stack; long long sum = 0; for(int i = 0; i < size; i++){ if(max_stack.empty() || array[max_stack.top()] > array[i]) max_stack.push(i); else if(array[max_stack.top()] < array[i]){ int cur = max_stack.top(); max_stack.pop(); if(!max_stack.empty()){ long big_one = array[max_stack.top()] > array[i] ? array[i] : array[max_stack.top()]; long long height = big_one - array[cur]; sum += height * (i - max_stack.top() - 1); } i--; }else{ continue; } } cout << sum << endl; }
package niuke; import java.util.Scanner; public class Main{ public static void main(String args[]){ Scanner in = new Scanner(System.in); int num = in.nextInt(); int [] height = new int[num]; for(int i =0;i<num;i++){ height[i] = in.nextInt(); } int left = 0; int right = height.length-1; int left_max = 0; int right_max = 0; int res = 0; while(left<right){ if(height[left]<height[right]){ if(height[left]<left_max) res = res+left_max - height[left]; else left_max = height[left]; left++; }else{ if(height[right]<right_max) res = res+right_max-height[right]; else right_max = height[right]; right--; } } System.out.println(res); } }
#include <bits/stdc++.h> using namespace std; int main(){ int n; cin >> n; if(n<=0) return 0; int arr[n]; for(int i=0; i<n; i++){ cin >> arr[i]; } int i=0, j=n-1, left=arr[0], right=arr[n-1]; long long sum_val=0; while(i<j){ if(left < right){ i ++; if (arr[i] >= left){ left = arr[i]; continue; } sum_val += (left-arr[i]); } else{ j--; if(arr[j]>right){ right = arr[j]; continue; } sum_val += (right-arr[j]); } } cout << sum_val; return 0; }
N = int(input()) nums = list(map(int, input().split())) res = 0 maxH = max(nums) idx = nums.index(maxH) leftH,rightH = 0, 0 for i in range(idx): if nums[i] < leftH: res += (leftH - nums[i]) else: leftH = nums[i] for i in range(N-1, idx, -1): if nums[i] < rightH: res += (rightH - nums[i]) else: rightH = nums[i] print(res)