首页 > 试题广场 >

容器盛水问题

[编程题]容器盛水问题
  • 热度指数：4970 时间限制：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

备注:

算法知识视频讲解
开通博客
头像 红玉圆
发表于 2020-05-12 19:08:56
题目描述给定一个整形数组arr，已知其中所有的值都是非负的，将这个数组看作一个容器，请返回容器能装多少水。输入描述:第一行一个整数N，表示数组长度。接下来一行N个数表示数组内的数。输出描述:输出一个整数表示能装多少水。 输入63 1 2 5 2 4输出复制5 思路：对于L位置，其水平线为min{左数 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 总之就是非常可爱
发表于 2022-02-15 14:30:06
//本题的暴力解为对于每一个位置都求出左边的最大值和右边的最大值然后求出当前位置的盛水量 //这种方法简单但时间复杂度高O（N²） //还可以进行预处理时间复杂度可以降至O（N）但是时间复杂度为O（N） //这两种方法较为简单这里用最优解可以做到时间复杂度为O（N）空间复杂度为O（1） #inclu 展开全文
去ta的博客 赞 (1) 回复(1) 收起
头像 快支棱起来的椰子很愤怒
发表于 2022-01-20 16:42:18
n = int(input()) if n < 3: print(0) exit() nums = list(map(int, input().split())) i, j = 0, n - 1 left_max = nums[0] right_max = nums[-1] r 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 龟行
发表于 2022-03-28 15:28:26
特别需要注意数据的输入输出的范围，确定合适的数据类型，不然会溢出 注意sum+=width*height; 以及sum需要定义为long型 ">#include<stack> using namespace std; int main(){ int n; scanf(" 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 WYJ96
发表于 2021-08-13 03:02:39
/*方法1 时间复杂度O(N^2) i位置上方的水= max{min{i左侧最大值，i右侧最大值}-arr[i],0} * */ public static int getWater1(int[] arr) { if (arr == null || 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

容器盛水问题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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