LeetCode_11.盛最多水的容器

难度:中等

关注博主,持续输出优质算法内容

题目链接

作者原始思路

1.动态规划的代码实现

class Solution {
    public int maxArea(int[] height) {
        var len = height.length;
        var statistical = new int[len][len];
        var maxSize = 0;
        var size = 0;
        for (int i = 1; i < height.length; i++) {
            for (int j = i; j < height.length; j++) {
                size = Math.min(height[j-i],height[j]) * i;
                statistical[i][j] = size;
                if (statistical[i][j] > maxSize) {
                    maxSize = statistical[i][j];
                }
            }
        }
        return maxSize;
    }
}

 存在问题

2. 不填表,直接运算

class Solution {
    public int maxArea(int[] height) {
        var len = height.length;
        var maxSize = 0;
        var size = 0;
        for (int i = 1; i < height.length; i++) {
            for (int j = i; j < height.length; j++) {
                size = Math.min(height[j-i],height[j]) * i;
                if (size > maxSize) {
                    maxSize = size;
                }
            }
        }
        return maxSize;
    }
}

 存在问题

3.反省

•  动态规划算法和分治算法并不是万能的,他们需要运用于能把复杂问题分解成一个简单问题,这个简单问题的性质和原来的问题的性质需要保持一致
• 注意的是,动态规划算法的下一个问题往往与上一个问题有联系,在此处,虽然可以把复杂的问题简单化后,问题的性质一样,但是,下一个问题与上一个问题往往产生不了联系,所以,这里强行用动态规划反而使得程序变得冗余,效率变低

官方解法-双指针解法

1.思路分析

• 1首先我们先要确定影响盛水面积的影响因素有哪些
  • 1,1.底面积,即两个下标之间的宽度
  • 1.2.高,即下标对应的值,由于木桶效应,决定盛水面积的是两条边中较短的边
• 2.其次,我们分析第一个因素,为了我们的面积可以达到最大,我们应该要让其下标间的宽度达到最大,即左索引与右索引分别初始化为最两端
• 3.最后,我们分析第二个因素,为了我们的面积可以达到最大,我们需要移动较短的一边
  • 3.1如果移动较长的一边,移动后宽度变小,无论移动后它是否成为较短的一边,面积一定会减少,即如果移动后不是较短的一边,说明另一边仍然是较短的一边,宽度减少,面积减少,如果是,不仅宽度减少,高度还减少了,所以,移动较长的一边是不可取的
• 4,双指针的核心问题即初始化和移动都解决了,代码就完成了

2.代码实现

class Solution {
    public int maxArea(int[] height) {
        var left = 0;
        var right = height.length - 1;
        var maxSize = 0;
        while (left < right) {
            maxSize = Math.max(Math.min(height[left],height[right])*(right - left),maxSize);
            if (height[left] < height[right]) {
                left++;
            }else {
                right--;
            }
        }
        return maxSize;
    }
}

代码分析:

• 1.注意每一次移动前都要算出当前的面积即可,调用了Math类的两个求较大值和较小值的方法
• 2.注意:题解中讲述到如果移动较短边时,发现边相等直接跳过,减少计算次数,这里并没有体现
• 原因:因为这会让程序多出循环,不仅达不到提高效率的效果,反而降低了程序的效率,所以,直接计算即可

结论

        博主刷题有限,不能准确讲出来什么时候用什么算法,但是将来的一天,我会充满信心的告诉大家什么时候用双指针,什么时候用其他的,最后我来总结一下几点

        1.双指针为什么这么定义和移动

        2.动态规划算法使用的前提