Java解决贪心法解决盛水问题

贪心法定义： 

   贪心算法是一种常见的解决优化问题的算法，其基本思想是在问题的每个决策阶段，都选择当前看起来最优的选择，即贪心地做出局部最优的决策，以期获得全局最优解贪心法的基本思路是从问题的某一个初始解出发，通过每一步的最优解，逐步逼近给定的目标，以尽可能快地求得更好的解。当达到算法中的某一步不能再继续前进时，算法停止。

贪心法盛水问题介绍：

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。

基本思想：

处理方式：

两边向中间遍历，每次移动最短的那一条边，计算盛水量，与最大容积作比较。

为什么要移动最短的那一条边？

只要移动肯定会使其x轴区域减少，如果移动左右两条边中最长的那个边，因为木桶效应容积必然会减少。每次移动最短的那条边就是贪心法中的局部最优解。

Java代码实现：

package 贪心法;

import static java.lang.Math.*;

public class 盛水问题 {
    public static void main(String[] args) {
        //定义每个板子的高度
        int[] height = {1, 8, 6, 2, 5, 4, 8, 3, 7};
        //定义开始索引
        int begin = 0;
        //定义结束索引
        int end = height.length - 1;
        //定义最大盛水量
        int max = 0;
        //定义最大盛水量时左右边板子序号
        int r = 0;
        int l = 0;
        //定义x轴每一个格子宽度
        int wide = 3;
        while (begin != end) {
            //计算盛水量a
            int a = wide * (end - begin) * min(height[begin], height[end]);
            System.out.println("当前盛水量:" + a);
            System.out.println("左边索引:" + begin + "右边索引:" + end);
            //如果成水量a大于当前max，则更新max
            if (a > max) {
                max = a;
                r = end + 1;
                l = begin + 1;
            }
            //移动这两条边中最小的边
            if (height[begin] > min(height[begin], height[end])) {
                end--;
                System.out.println("右边移动一次");
            } else {
                begin++;
                System.out.println("左边移动一次");
            }
        }

        System.out.println("左边板高度:  " + height[begin] + "    左边第" + l + "个板子" +
                "\n右边板高度:  " + height[end] + "  右边第" + r + "个板子"
                + "\n最大盛水量: " + max);
    }
}