11. 盛最多水的容器-双指针法

冷不防 2023-02-08 12:49 3阅读 0赞

> 思路简单，代码清晰。

# 题目 #

链接：https://leetcode-cn.com/problems/container-with-most-water

给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器。

示例 1：  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAa2tra2s3MjEw_size_20_color_FFFFFF_t_70_g_se_x_16]

输入：[1,8,6,2,5,4,8,3,7]
    输出：49 
    解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。
    在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

输入：height = [1,1]
    输出：1

示例 3：

输入：height = [4,3,2,1,4]
    输出：16

示例 4：

输入：height = [1,2,1]
    输出：2

提示：

n == height.length  
2 <= n <= 10^5  
0 <= height\[i\] <= 10^4

# 题目分析 #

这道题，把数组元素看成容器的木板，下标之差看成容器的长度。

容器的盛水量 = 短板的高度 \* 下标之差

最简单的粗暴的解法是双重循环：

1.  外层循环，下标 i 固定左边的木板 height\[i\]
2.  内层循环移动 j ，得到右边的木板 height\[j\]
3.  盛水的高度取决于较短的木板，因此取 height 较小值 ，乘以下标之差 (j - i)
4.  比较得数和之前算的结果，取较大值。最后就得到结果

class Solution {
        
        public int maxArea(int[] height) {
        
            int ans = 0;
            for (int i = 0; i < height.length ; i++) {
        
    
                for (int j = height.length - 1; j > i;  j--) {
        
                    int v = Math.min(height[i],height[j]) * (j-i); // 当前的盛水量
                    ans = Math.max(ans , v); // 取较大的盛水量
                }
    
            }
            return ans;
        }
    }

# 双指针优化 #

对刚才的解法进行优化，优化的思路必定是减少一轮循环。  
像这类面试热门题目，一般有一眼想到的解法，以及经过优化后最终 O(n) 的解法。  
毕竟，面试官才不会选一道没有技巧的题目。

暴力法的缺点是对于一轮循环，仅移动一个方向的木板。而双指针能做到一轮循环中，移动两个方向的木板。移动 height 较小的指针。

我举个例子理解双指针的思路，我以题目的例1来说明：

1.  height\[0\] 是最短的木板，值为1
2.  上面的暴力法，是从右往左，移动右边的模板。右边的模板从下标8，向左移动。
3.  第一次计算得 height\[0\] \* (8 - 0) = 8 ，它是外层循环为 height\[0\] 的最大值；继续移动右边的 j，向左移动到 7 ，height\[0\] \* (7 - 0) = 7，可以预见，只会越算越小。
4.  此时没必要移动右标的下标，而是移动左边下标，使 i 移动到 1 的位置。由于 height\[1\] 比 height\[8\] 大， 取 height\[8\] 作为高度， 计算 height\[8\] \* (8 - 1) = 49。

归纳一下，刚才当 i = 0 时，无论我们怎么移动右指针，得到的容器的容量都小于移动前容器的容量，于是移动左指针 。于是，双指针的解法就是，每次移动 height 较小的下标。

class Solution {
        
        public int maxArea(int[] height) {
        
            int i = 0;
            int j = height.length - 1;
            int ans = 0;
            while (i < j) {
        
                int result = Math.min(height[i], height[j]) * (j - i);
                ans = Math.max(ans, result);
                if (height[i] < height[j]) {
        
                    i++;
                } else {
        
                    j--;
                }
            }
            return ans;
           
        }
    }

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAa2tra2s3MjEw_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
推荐看看 LeetCode 对这道题的官方题解  
本篇完

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAa2tra2s3MjEw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20230208/9e62adae56cc4eeaa1dc27ced5bf0b09.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAa2tra2s3MjEw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20230208/a6333c93d909421a8ed0b6705e3b7e95.png