今日算法题：

题目

错误·题解

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """

        right = len(height) - 1
        max_Area = 0 

        for left in range(len(height)):
            Area = (right - left) * min(height[left],height[right])
            max_Area = max(Area,max_Area)

            right-=1 
        print(max_Area)

采用的是单指针（left 循环，right 每次减 1）的方式

这种方式不能遍历到所有可能的两条线组合，会错过能构成最大面积的情况。你的代码让 left 从 0 递增，同时 right 从末尾递减，每次循环两者同时移动（left+1 且 right-1）。这种方式会跳过绝大多数可能构成最大面积

的两条线组合。

比如示例中：

例如对于输入 [1,8,6,2,5,4,8,3,7]：

你的代码只会检查 (1,7)、(8,3) 等这几对组合

而正确的最大面积组合 (1,8) 根本不会被检查到

题解

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """



        right = len(height) - 1
        max_Area = 0 
        left = 0

        while left < right:
            width = right - left
            h =min(height[right],height[left])
            Area = width * h
            max_Area = max(Area,max_Area)

            if height[left] < height[right]:
                left+=1
            else:
                right-=1

        return max_Area            



        return max_area

核心思路

使用两个指针：

• left 指向最左边竖线，right 指向最右边竖线。

计算容量：

area = (right - left) * min(height[left], height[right])

两个指针从两边开始，初始时right>left ，求了这两个的面积，接着height[right]>height[left]

所以保留right高的，更换短板，left+1，

接着判断：right>left，求了面积，此时发现左边更高了

所以保留left高的，更换短板，right-1，

.....依次移动

一般两个指针相会即可结束。随着两个指针的相近，所围成面积的底长越来越短，所以面积也一般不会太大。

不太会出现两个相邻的柱子所围成的面积最大。

体现知识点

一、双指针（Two Pointers）

双指针就是在一个序列（数组、字符串、链表）上使用两个索引或指针，通过协调移动来减少无效遍历，从而优化时间复杂度。

常见场景

• 数组/字符串：

  • 快慢指针：去重、移动元素（如「283. 移动零」）。

  • 对撞指针：两端向中间靠拢（如「11. 盛最多水的容器」、「167. 两数之和 II」）。

  • 滑动窗口：一前一后控制窗口区间（如「3. 无重复字符的最长子串」）。

• 链表：

  • 快慢指针：找环、找中点（如「141. 环形链表」、「876. 链表的中间节点」）。

优化算法，避免 O(n²) 的双层循环，通过两个指针的相对移动，把复杂度降到 O(n)。

有序性利用：通常双指针依赖数据有序（递增、递减或隐含的区间性）。

经典例子

• 移动零：快慢指针，一个找非零，一个放置位置。

• 盛最多水的容器：对撞指针，从两端往中间收缩。

• 两数之和 II：数组有序，双指针逼近目标和。

• 无重复字符的最长子串：滑动窗口维护区间。

需要注意

1. 要先搞清楚：指针的移动条件是什么？如何移动。

2. 边界条件：left < right，或者窗口 [left, right] 怎么维护？

3. 有序性假设必须满足（比如数组有序才能用对撞指针做「两数之和」）。

---

二、贪心算法（Greedy）

贪心算法就是在求解过程中，每一步都求当前最优解（局部最优），希望通过这些选择得到全局最优解。

常见场景

• 区间问题：如活动选择、会议室安排（按结束时间排序 → 每次选能最早结束的）。

• 最小/最大覆盖：如「55. 跳跃游戏」「45. 跳跃游戏 II」。

• 构造问题：如拼接最大数、压缩问题。

• 排序 + 选择：比如零钱兑换（贪心能解某些币值体系）。

核心思想

关键点是：证明局部最优能推导出全局最优。通过保持当前值与最优值的最优对齐，维护一个“当前可达的最优状态”，再一步步更新。

经典例子

• 盛最多水的容器：每次丢弃短板，就是贪心思想。

• 跳跃游戏 II：每次在当前跳跃范围内，选择能跳得最远的下标。

• 区间调度：每次选最早结束的区间，保证后面能容纳更多。

需要注意

贪心并不是万能的，必须验证局部最优 → 全局最优。有些问题看起来能用贪心，实际上需要动态规划（如「零钱兑换」）。

---

过程困难

出现问题：贪心过程中双指针的移动方式不一定导向局部最优解。（来自舍友的问题）

来自舍友的题解：

具体问题就是：

在到达解（2-9）之后，按理来说和h(2)>h(9)，移动右边，计算（2-8）的面积。

但是看图思考一下可知，假设不移动右边，而是移动左边，计算（3-9）的面积，是比（2-8）大的

但在整个流程中是不会考虑（3-9）的，这样的移动是否会漏掉最优解？

总之就是，如果固定短的那个，长的那边无论多长，面积计算的一条边已经被短的固定，而另一条边因为要移动缩减，所以永远不会不会比之前的更大。

反之，如果固定长的那个，现在的最大值是被限制在这个固定的值上，如果后续移动那个短的在下次出现了更长的（比固定的更长），那么有可能值会更大

双指针法的 “移动较矮指针” 策略是经过严格推导的：所有被 “跳过” 的情况（比如移动另一个指针）的面积一定更小，因此不会漏掉最优解。

优化解法

最优解