计算题

""""
特殊的单调递增
序列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;
    }
}

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;
}

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;
    }

}

关键

找到最高的柱子，并确实其位置