首页 > 试题广场 >

容器盛水问题

[编程题]容器盛水问题
  • 热度指数：4961 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个整形数组arr，已知其中所有的值都是非负的，将这个数组看作一个容器，请返回容器能装多少水。
具体请参考样例解释

输入描述:
第一行一个整数N，表示数组长度。

接下来一行N个数表示数组内的数。


输出描述:
输出一个整数表示能装多少水。
示例1

输入

6
3 1 2 5 2 4

输出

5

说明
示例2

输入

5
4 5 1 3 2

输出

2

备注:

算法知识视频讲解
查看答案及解析
添加回答
Java
pein531头像 pein531
左右双指针，左边的最大高度减去左指针当前所在位置的高度，就是当前位置贡献的水量（因为最大高度把水拦住了），右指针同理。对于左右的最大高度，由于最终水量取决于矮的高度，因此每次移动所指位置矮的指针，左边最大高度矮于右边就右移左指针，反之左移右指针。 
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);
    }
}

发表于 2021-11-17 15:47:07 回复(0)
C/C++
nbgao头像 nbgao 
#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;
}

发表于 2020-03-17 07:41:16 回复(0)
LQW-A头像 LQW-A 
//单调栈
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;
}

发表于 2021-06-10 21:14:17 回复(0)
求求n年前同一专业的学长收下我吧头像 求求n年前同一专业的学长收下我吧
这题不是力扣上的接雨水吗，为什么我把力扣上这题的官方题解粘过来跑不过去
发表于 2021-03-07 16:43:34 回复(1)
亲亲猪儿虫头像 亲亲猪儿虫 
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);
    }
}

发表于 2021-03-06 11:26:07 回复(0)
Kai21头像 Kai21
直接贴代码，这是一种空间复杂度O(1)，时间复杂度为O(n)的算法，核心思路是双指针。
在每次迭代中，被访问的新节点i的左右边界最大值left和right一定是i左右最小的，这就是为什么if判断里，谁小谁走。（注意，返回值一定要用long long，测试例会进行大数爆破） 
#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;
}


发表于 2020-02-11 00:16:37 回复(0)
Python
汤普森30头像 汤普森30 
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)

发表于 2019-08-29 16:33:34 回复(0)
提交观点

问题信息

栈 高级结构 单调栈
上传者：小小
难度：
7条回答 11693浏览

热门推荐

通过挑战的用户

查看代码

相关试题

容器盛水问题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号