首页 > 其他 > 详细

容器盛水问题

时间:2017-09-24 11:16:17      阅读:489      评论:0      收藏:0      [点我收藏+]

一、问题描述

给定一数组ary,元素两两组合,以min{ary[i],ary[j]}为高,以跨度(j-i)为宽可组成一个容器,求所有这样的容器的最大面积maxVolume。

二、算法分析

以数组ary为例:
int[] ary = {3,2,6,8,1,7};
如果从蛮力法的角度来看。
相当于从以上6个元素中选两个不考虑排序,是组合问题。
C(n,m) = C(6,2) = 15
不难想到,遍历15种组合的volume值,然后取其最大值,定能够求解。
但是我们真的需要求15中全部的情况吗?
从另一个角度看来
有ary[0]=3参与的情况5种,这些情况中最大的volume为v1
剩余组合中,有ary[1]=2参与的情况4种,这些情况中最大的volume为v2
剩余组合中,有ary[2]=6参与的情况3种,这些情况中最大的volume为v3
剩余组合中,有ary[3]=8参与的情况2种,这些情况中最大的volume为v4
剩余组合中,有ary[4]=1参与的情况1种这些情况中最大的volume为v5
不难发现全局最大的volume = max{v1,v2,v3,v4,v5}

但是此处的v1,v2,v3,v4,v5求取有的是比较繁琐,原因在于参与的边选取得不合理,
在换个角度
有min{ary[0],ary[5]}=ary[1]参与的情况,5种,这些情况中最大的volume为v1,且v1必为(5-0)*ary[0]
剩余组合情况种,有min{ary[1],ary[5]}=ary[1]参与的情况,4种,这些情况中最大的volume为v2,且v2必为(5-1)*ary[1]
剩余组合情况种,有min{ary[2],ary[5]}=ary[2]参与的情况,3种,这些情况中最大的volume为v3,且v3必为(5-2)*ary[2]
剩余组合情况种,有min{ary[3],ary[5]}=ary[5]参与的情况,2种,这些情况中最大的volume为v4,且v4必为(5-3)*ary[5]
剩余组合情况种,有min{ary[3],ary[4]}=ary[4]参与的情况,1种,这些情况中最大的volume为v5,且v5必为(4-3)*ary[4]
全局最大的volume=max{v1,v2,v3,v4,v5}

关键在于:如果参与的边是序列两端的最小边:min{ary[i],ary[j]},则在这些局部组合情况中,局部最大volume必定等于min(ary[i], ary[j])*(j-i)。

三、java实现

    public static int getMaxVolume(int[] ary,int low,int high){
        int i = low,j = high;//两指针,一前一后
        int maxVolume = 0;
        while(i<j){
            //容器的容量以ary[i]和ary[j]中较短边为高,跨度为宽
            maxVolume = Math.max(Math.min(ary[i], ary[j])*(j-i), maxVolume);
            if (ary[i]<ary[j]) {//移动的始终是短边
                i++;
            }else {
                j--;
            }
        }
        return maxVolume;
    }

 

容器盛水问题

原文:http://www.cnblogs.com/qcblog/p/7586582.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!