算法题目——蓄水池问题

秒速五厘米 2022-05-12 07:44 226阅读 0赞

![1536313650228ab52a8ce6b][]

**题目： 给出了指定高度的任意两个板子，每个木板位置间隔相等，由你随机组合，怎么实现装最多的水。**

分析：假设水池厚度相同，于是水容量计算公式：

水容量 = 板子距离\*板子高度

板子距离：两元素的索引之差

板子高度：两元素的最小值

解题思路：

看到这道题目，首先可以肯定的是用穷举法肯定能解决，这里就不多介绍了，大家可以参考一下这篇文章

[https://blog.csdn.net/weixin\_42621338/article/details/82710133][https_blog.csdn.net_weixin_42621338_article_details_82710133]。

这里我们采用的方法是：

1、 从最大宽度开始（即从数组两端开始，左记为L,右记为R），求出最大宽度下的面积，比较两端口位置的值；

2、对值较小的一边的端口索引值进行调整（左端口的话+1，右端口的话-1）；

3、比较变化后的端口位置上的值是否大于调整前的值，是的话执行第4步，否则先判断左端口是否仍小于右端口索引值，是的话再次执行第二步，否的话执行第4步；

4、计算此宽度下的最大面积，与最大面积比较，保留最大面积值，判断左端口索引值是否仍小于右端口索引值，是的话再次执行第二步（缩小宽度），否的话跳出循环；

上面方法第三步主要是减少不必要的求面积操作，加快比较速度。

实现代码如下：

package com.liao.algorithm;
    
    import java.util.Random;
    
    public class WaterTank {
    	public static void main(String[] args) {
    		int len = 10;
    		int max = 10;
    		WaterTank wt = new WaterTank();
    		// 生成一个随机数组
    		int[] ns = wt.generateArray(len, max);
    		wt.seekMaxArea(ns);
    	}
    
    	/*
    	 * 生成一个随机数组 数组长度为n,数组中最大值为max
    	 */
    	public int[] generateArray(int n, int max) {
    		int[] ns = new int[n];
    		for (int i = 0; i < n; i++) {
    			Random ran = new Random();
    			ns[i] = ran.nextInt(max) + 1;
    			System.out.print(ns[i] + ",");
    		}
    		return ns;
    	}
    
    	/*
    	 * 寻找最大面积 从 数组两端开始
    	 */
    	public void seekMaxArea(int[] ns) {
    		int l = ns.length;// 数组长度
    		int i = 0;// 数组前端
    		int j = l - 1;// 数组后端
    		int max = 0;// 初始最大面积
    		int s, a;//中间变量
    		while (i < j) {
    			if (ns[i] < ns[j]) {
    				a = i;
    				while (ns[a] >= ns[++i] && i < j) {
    					//ns[a]不小于ns[++i]且i小于j，则i继续加1,无需跳出循环求面积再做比较
    					continue;
    				}
    			} else {
    				a = j;
    				while (ns[a] >= ns[--j] && i < j) {
    					//ns[a]不小于ns[--j]且i小于j，则j继续减1,无需跳出循环求面积再做比较
    					continue;
    				}
    			}
    			s = (j - i) * Math.min(ns[i], ns[j]);//求此时的面积
    			if (s > max) {
    				max = s;
    			}
    		}
    		System.out.println("最大蓄水量为" + max);
    	}
    }

[1536313650228ab52a8ce6b]: http://p3.pstatp.com/large/pgc-image/1536313650228ab52a8ce6b
[https_blog.csdn.net_weixin_42621338_article_details_82710133]: https://blog.csdn.net/weixin_42621338/article/details/82710133