Leetcode

yedou2026/2/13大约 3 分钟

双指针

题目大意：给定一个数组 height，每个数代表坐标轴上一个高度为 height[i] 的垂直线。找两条线，使得它们与 x 轴构成的容器能容纳最多的水。

核心公式： $面积 = \min(左高度, 右高度) \times 宽度(右索引 - 左索引)$
双指针策略：头尾指针，向内收缩。
- 设置 left = 0, right = n-1。
- 关键点：每次移动较矮的那一边。
为什么移动矮的那边？
- 如果你移动高的那边，宽度变小了，而容器的高度（由短板决定）只会不变或者变得更小，面积一定变小。
- 只有移动矮的那边，虽然宽度变小了，但如果能遇到一个更高的板子，面积才有机会变大。
复杂度：时间 $O(N)$ ，空间 $O(1)$ 。

题目大意：给你一个整数数组，找出所有和为 0 且不重复的三元组。

双指针策略：排序 + 固定一个数 + 双指针。
1. 先排序（这是使用双指针的前提）。
2. 遍历数组，固定第一个数 nums[i]。
3. 在 i 之后的区间内，设置 left = i + 1 和 right = n - 1。
4. 计算 sum = nums[i] + nums[left] + nums[right]：
  - sum < 0：说明数小了，left++。
  - sum > 0：说明数大了，right--。
  - sum == 0：找到一组结果，保存，并同时收缩 left 和 right。
难点：去重
- 为了不找到重复的三元组，在移动 i、left、right 时，如果发现下一个数和当前数一样，就直接跳过。
复杂度：时间 $O(N^2)$ ，空间 $O(1)$ （不计排序开销）。

题目大意：给定 n 个非负整数表示每个柱子的高度，计算下雨后能接多少雨水。

核心逻辑：对于位置 i 能接多少水，取决于它左右两边“最高柱子”中的较小值。
- $当前位水量 = \max(0, \min(左侧最高, 右侧最高) - 当前高度)$
双指针策略：头尾指针，维护动态最值。
1. 设置 left = 0, right = n-1。
2. 维护两个变量 left_max（左边出现过的最高高度）和 right_max（右边出现过的最高高度）。
3. 关键点：比较 height[left] 和 height[right]。
  - 如果 height[left] < height[right]：说明左边的瓶颈在于 left_max。因为即便右边还有更高的，决定水位的也是较小的那一侧。此时处理 left：
    - 更新 left_max。
    - 累加 left_max - height[left]。
    - left++。
  - 反之，处理 right 侧，逻辑对称。
复杂度：时间 $O(N)$ ，空间 $O(1)$ 。相比于用数组记录前向/后向最大值的 DP 解法，双指针将空间复杂度优化到了常数级别。

题目	指针初始位置	移动逻辑	核心思想
盛水最多的容器	首、尾	移动较矮的指针	贪心：尝试通过牺牲宽度换取高度增加
三数之和	固定 `i`，`left=i+1`, `right=n-1`	根据 sum 与 0 的关系移动	搜索：在有序区间内逼近目标值
接雨水	首、尾	移动较矮的一侧，并更新该侧最大值	瓶颈原理：水位由左右两边最高的“短板”决定