题目主要信息:
给定一个整型数组，数组每个元素表示下图所示的每列灰色柱子高度，数值都是非负数
在雨水（图中蓝色部分）不超过边界的情况下，问最多能有多少蓝色的格子
数组以外的区域高度视为0
举一反三：
BM93. 盛水最多的容器
方法：双指针(推荐使用)
知识点：双指针
双指针指的是在遍历对象的
展开全文
public static long maxWater(int[] arr) {
if (arr == null || arr.length <= 2) {
return 0;
}
int left = 0, right
展开全文
1，三指针求解
这题让求柱子中间能盛多少水，首先可以肯定两边的两个柱子是不能盛水的，只有两边之间的柱子有可能会盛水。最简单的一种方式就是使用3个指针，先找到最高的柱子，用一个指针top指向最高柱子，然后最高柱子左边用两个指针，一个left，一个right（这里的left和right指向柱子的高度）。
展开全文
遍历两遍，从左往右遍历保存当前最大值，从右往左遍历保存当前最大值，然后容水量为 两次遍历最大值中的最小值减去当前arr[i]。累加起来即可。 class Solution {
public:
/**
* max water
* @param arr int整型vector
展开全文
暴力求解法 开始时想到了暴力求解法，最差情况下是O(nn)的时间复杂度，很不幸，超时了。但至少在面试的时候，可以在有限的时间内给出一个基本解法，思路是这样的：1 在数组arr(left, right)中找出最大和第二大的数的位置pos1和pos2；这样就将arr划分成了3段： left,...,
展开全文
本题的题目描述不太明确，需要一张示意图，在看别人的题解时看到这个图才明白是怎么回事。 所以本题的核心就是构造两边高而中间低的桶，这个桶能装的水取决于两边里面比较短的那一边。比如{3，1，2} 这个数组能装的水等于1 求得两边的最小值 22 用短的边减去中间波谷的值1得到结果1则数组{3，1，2} 这
展开全文
很多人是没有理解题目，下面是别人的代码问题的关键是找到最小边界。如图 import java.util.*;
public class Solution {
/**
* max water
* @param arr int整型一维数组 the array
展开全文
题目可以转化为求每个位置上面能装多少水比如题目中给出来的例子：左右两边边界(0和5位置)上是一定不会有水的，然后1位置上能装2格水，2位置上能装1格水，3位置上不能装水，4位置上能装2格水。所以对于这一个例子来说，一共能装5格水。那么我们就再来考虑一下，每个位置上面能装多少水怎么求对于位置 来说，
展开全文
朴素解法 对于每根柱子而言，我们只需要找出「其左边最高的柱子」和「其右边最高的柱子」。 对左右的最高柱子取一个最小值，再和当前柱子的高度做一个比较，即可得出当前位置可以接下的雨水。 同时，边缘的柱子不可能接到雨水（某一侧没有柱子）。 这样的做法属于「暴力做法」，但题目没有给数据范围，我们无法分析到底
展开全文
思路分析：因为要该容器是一个高低不平的容器，所以我们直接找出容器的左右边界，很明显，为了不让水溢出来，容器的边界肯定取那个更低的。然后使用双指针，分别从两边往中间扫描，如果此时左边arr[left]的高度小于右边的高度时，左指针向右扫描+1，如果此时当前位置的高度小于容器的边界高度，那么意味着此位置
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
