一、题目

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

示例1
输入：[1,8,6,2,5,4,8,3,7]
输出：49

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

二、算法知识

2.1 双指针

双指针是一种在数组、链表或字符串等线性数据结构中常用的算法技巧。其核心思想是使用两个指针（或索引）协同遍历数据结构，通过指针的移动规则和相对位置关系，高效地解决特定问题。这种方法通常能将时间复杂度从 $O(n^2)$ 优化到 $O(n)$ 或 $O(n\log n)$。

主要类型与应用场景

1. 快慢指针

   • 原理：两个指针从同一位置（如链表头或数组起点）出发，但移动速度不同（如快指针每次移动两步，慢指针每次移动一步）。
   • 典型应用：
     • 判断链表是否有环：若快指针追上慢指针（相遇），则有环；若快指针到达末尾（null），则无环。
     • 寻找链表中间节点：快指针到达末尾时，慢指针正好在中间。
     • 寻找链表的倒数第 k 个节点：快指针先走 k 步，然后两者同速前进，快指针到末尾时，慢指针即为所求。
   • 示例代码（链表判环）：

     def has_cycle(head):
         slow = head
         fast = head
         while fast and fast.next:
             slow = slow.next
             fast = fast.next.next
             if slow == fast:
                 return True
         return False
     

2. 左右指针（对撞指针）

   • 原理：两个指针分别指向数据结构的两端（如数组首尾），并向中间移动，根据条件决定移动哪个指针。
   • 典型应用：
     • 有序数组的两数之和：通过比较 arr[left] + arr[right] 与目标值的大小，调整左右指针。
     • 反转数组：交换 left 和 right 所指元素，并向中间移动。
     • 验证回文串：比较左右指针所指字符是否相等。
   • 示例代码（反转数组）：

     def reverse_array(arr):
         left, right = 0, len(arr) - 1
         while left < right:
             arr[left], arr[right] = arr[right], arr[left]
             left += 1
             right -= 1
         return arr
     

3. 滑动窗口

   • 原理：两个指针（通常称为 left 和 right）共同定义数据结构的一个子区间（窗口）。右指针负责扩大窗口，左指针负责缩小窗口，根据条件动态调整窗口大小。
   • 典型应用：
     • 求最小覆盖子串：通过移动右指针扩展窗口直到包含所有目标字符，再移动左指针收缩窗口以优化长度。
     • 求最长无重复子串：右指针扩展时记录字符位置，遇到重复时左指针跳到重复字符的下一位。
     • 固定长度的子数组问题（如求平均值）。
   • 示例代码（求最长无重复子串）：

     def longest_unique_substring(s):
         char_map = {}  # 存储字符最近出现的位置
         left = max_len = 0
         for right in range(len(s)):
             if s[right] in char_map:
                 left = max(left, char_map[s[right]] + 1)
             char_map[s[right]] = right
             max_len = max(max_len, right - left + 1)
         return max_len
     

优势

• 时间复杂度优化：通常能将嵌套循环（$O(n^2)$）优化为单次遍历（$O(n)$）。
• 空间复杂度低：通常只需常数级额外空间（$O(1)$）。
• 逻辑清晰：指针移动规则直接映射问题逻辑。

注意事项

• 边界条件：需明确指针移动的终止条件（如 left < right 或 fast != null）。
• 指针移动规则：需根据问题要求精确设计指针的移动策略。
• 数据结构特性：适用于数组、链表等线性结构，不适用于树或图等非线性结构。

双指针是解决线性数据结构问题的利器，掌握其核心思想和常见模式，能显著提升算法解题效率。

三、题解

3.1 题解1

思路：
首先很容易想到，从数组中选出两个数，然后计算它们围成的区域面积大小，最后返回最大的面积。

面积的计算方法：底为下标之差，高为两数中更小的数。

class Solution:
    def maxArea(self, height: List[int]) -> int:
        n = len(height)
        max_s = 0
        for i in range(n-1):
            for j in range(i+1,n):
                s = (j-i)*min(height[i],height[j])
                if s>max_s: max_s = s
        return max_s

由于时间复杂度为$O(N^2)$，所以当数组长度很大时，需要非常大的时间，可能会超出时间限制。

3.2 题解2

思路：双指针
使用两个指针，分别指向数组的两端，计算当前所围成的面积，由于面积计算公式为：

两个指针指向的数字中较小值∗指针之间的距离
即容量取决于短板

如果移动数字较大的那个指针，「两个指针指向的数字中较小值」 不会增加， 「指针之间的距离」 会减小，那么这个乘积会减小。因此，移动数字较大的那个指针是不合理的，移动数字较小的那个指针。

最终答案就是每次以双指针为左右边界（也就是 「数组」 的左右边界）计算出的容量中的最大值。

class Solution:
    def maxArea(self, height: List[int]) -> int:
        n = len(height)
        max_s = 0
        i=0
        j=n-1
        while (i < j):
            if height[i]<height[j]:
                h = height[i]
                s = (j-i)*h
                i+=1
            else:
                h = height[j]
                s = (j-i)*h
                j-=1
            if s>max_s: max_s = s
        return max_s

力扣官方题解：

class Solution:
    def maxArea(self, height: List[int]) -> int:
        n = len(height)
        max_s = 0
        i=0
        j=n-1
        while (i < j):
            s = (j-i)*min(height[i],height[j])
            max_s = max(s,max_s)
            if height[i]<height[j]:
                i+=1
            else:
                j-=1
        return max_s

复杂度分析

• 时间复杂度：O(N)，双指针总计最多遍历整个数组一次。

• 空间复杂度：O(1)，只需要额外的常数级别的空间。