首页 > 试题广场 > 计算题
[编程题]计算题
给定n个非负整数表示每个宽度为1的柱子的高度题,计算按此排列的柱子,下雨之后能接多少雨水。

输入描述:
逗号分隔的整数,表示每根柱子的高度。
柱子数n<=1000000,每根柱子的高度不大于100000


输出描述:
雨水量(高度和)
示例1

输入

0,1,0,2,1,0,1,3,2,1,2,1

输出

6
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;
    }
}
发表于 2019-07-30 16:56:44 回复(0)
""""
特殊的单调递增
序列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)
发表于 2019-07-14 18:44:02 回复(0)
#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%

编辑于 2019-07-04 16:00:31 回复(1)
#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;
}

编辑于 2019-08-15 10:41:35 回复(0)
hhh,超时。
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)

发表于 2019-07-12 10:08:49 回复(0)
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;
    }

}

关键

找到最高的柱子,并确实其位置
发表于 2019-06-13 22:40:40 回复(0)