企业官网建设流程全解析

最长连续序列和盛最多水的容器，这两道题我刷了很多遍，也看着不少同事在面试前临时抱佛脚。它们看着毫无关联，一个是哈希表的经典应用，一个是双指针的入门必刷，但放在一起其实特别能说明问题：数组类题目里最常用的两种优化思路，恰好被这两道题各占了一样。一个是空间换时间，把查找降到O(1)级别；一个是缩减搜索空间，用双指针把O(n²)暴力扫成O(n)。如果你正准备算法面试，或者只是想把数据结构与算法的基础打牢，这两道题值得一起琢磨透。

先说清楚，这篇文章不是单纯贴题解。我会把每一步选择背后的“为什么”讲明白，比如128题为什么要用HashSet、为什么只有序列起点才往后扩展，11题为什么永远移动矮的那一边、怎么向面试官证明这个贪心是对的。这些细节才是面试里真正被追问的东西，也是你刷完题之后能迁移到其他题目的底层能力。

1. 两道题为什么值得放在一起刷

1.1 面试中的真实定位

先说最长连续序列（128题），这题在面试里出现频率相当高。它最狠的地方在于时间复杂度要求O(n)，而大多数人第一反应是排序，排序完再扫一遍连续段，复杂度O(n log n)，直接不满足要求。这题的考察点很明确：你是不是能在“数组无序、要求线性时间”的条件下，想到用哈希表来空间换时间。很多公司的笔试环节会把它作为中等题出现，但说实话，它的代码量很小，真正的难点在思路上。

盛最多水的容器（11题）则是双指针类题目的经典代表，双指针这名字听起来唬人，其实核心就是两个下标从两端往中间走，每次移动其中一个。这题是很多面试官爱用来考察“你有没有证明习惯”的题：暴力解法写出来谁都会，但你能不能用逻辑说明双指针为什么不会漏掉最优解。我见过不少候选人能写出双指针代码，但被追问“为什么这样就是对的”时卡住了，这点非常可惜。

这两道题看似独立，其实共享同一个底层逻辑：先想清楚暴力解法为什么浪费，再去找浪费在哪里，最后设计一种机制把浪费的遍历省掉。128题的浪费在于重复扫描了同一个序列的中间段，11题的浪费在于有很多种左右柱子的组合其实不可能成为答案。带着这个视角去刷，效果远好于背题解。

1.2 一道题一个核心思想

如果给这两道题各提炼一个关键词，128题是“集合判重”，11题是“单调收敛”。

128题的核心是：用HashSet把所有数组元素存起来，使每个元素的查询成本变成O(1)。接下来找序列的起点，什么时候一个数字是某个连续序列的起点？当num-1不存在于集合中时，num就是起点。只有从起点开始往右数，才能不重复地覆盖整个序列。

11题的本质则是利用了一个很直观的数学事实：容器的盛水量由两条柱子中较矮的那条决定，也就是短板效应。那么当left和right指向两条柱子时，如果移动较高的那条，无论新柱子多高，水量都不可能超过当前值；只有移动较矮的那条，才有机会让短板变高，从而让总面积变大。这个“移动矮的”策略，就是双指针收敛的合理性来源。

我一直觉得刷算法题不应该追求数量，而应该把每一道题背后的优化思想抠出来。这两道题恰好是两种最典型的优化范式，把它们放进同一篇文章里详细拆解，比单刷十道同类题更有价值。下面我分开细讲。

2. 128. 最长连续序列：空间换时间的最优解

2.1 题面回顾与常见误区

题目很简短：给你一个未排序的整数数组 nums，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。比如 nums = [100, 4, 200, 1, 3, 2]，最长连续序列是 [1, 2, 3, 4]，长度是 4。要求设计一个时间复杂度为 O(n) 的算法。

我第一次做这道题的时候，脑子里的第一个念头也是排序。排序完，相邻元素如果差值为1就可以扩展连续序列，但坑在于：第一，排序本身O(n log n)，题设不允许；第二，数组里可能有重复元素，比如 [1, 2, 0, 1]，排序后是 [0, 1, 1, 2]，连续序列 [0,1,2] 长度是3，但如果处理不好重复值，很容易在相邻相等时错误地断开。所以光是“排序后扫描”这一条路，就不满足线性时间要求。

还有人会想暴力双重循环：枚举每个元素作为起点，然后不断查找 num+1、num+2 是否在数组里。这个思路本身没问题，但如果没有用哈希表，每次查找都要O(n)，整个就是O(n³)；即使用了哈希表，如果对每个元素都往后扩展，最坏情况下比如整个数组就是 [1,2,3,...,n] 时，从每个数字都往后数一遍，时间复杂度会退化成O(n²)。这两个坑几乎是人人都会踩的。

2.2 核心思路：从“集合”和“序列起点”两个角度切入

要理解最优解，只需要抓住两个关键点。

第一个关键点是去重与查询。把数组所有元素放进一个 HashSet，一方面自动去掉了重复的干扰，另一方面让任意一个值的查询时间变成O(1)。为什么去重很重要？因为连续序列关心的是“值存不存在”，而不是“这个值出现过几次”。比如 [1, 2, 2, 3]，连续序列 [1,2,3] 只需要值1、2、3存在，重复的2不会让序列变长。

第二个关键点是只在序列的起点处开始扩展。假设当前枚举到的数字是 x，如果 x-1 不在 HashSet 里，那 x 就是某个连续序列的起点，我们从 x 开始，不断检查 x+1、x+2、x+3……直到断掉为止。如果 x-1 已经在集合里，说明 x 不是这个连续序列的起点，就不需要从它开始往后扩展，直接跳过。

这个“只从起点开始”的优化是整个算法的灵魂。它保证了每个连续序列只会被完整扫描一次，而不是从每个元素往后各扫一遍。可以这么类比：有一排多米诺骨牌，如果你从每一张牌都开始推一次，那大部分推倒动作都重复了；只有从最左边那张开始推，整个序列才被完整推倒一次，且不重复。

2.3 完整代码与复杂度推导

Java 版本的实现如下：

class Solution { public int longestConsecutive(int[] nums) { if (nums == null || nums.length == 0) { return 0; } Set<Integer> set = new HashSet<>(); for (int num : nums) { set.add(num); } int maxLen = 1; for (int num : set) { if (!set.contains(num - 1)) { int cur = num; int len = 1; while (set.contains(cur + 1)) { cur++; len++; } maxLen = Math.max(maxLen, len); } } return maxLen; } }

用 Python 写更简洁：

class Solution: def longestConsecutive(self, nums: List[int]) -> int: num_set = set(nums) max_len = 0 for num in num_set: if num - 1 not in num_set: cur = num length = 1 while cur + 1 in num_set: cur += 1 length += 1 max_len = max(max_len, length) return max_len

空间复杂度O(n)很好理解，因为额外开了一个哈希集合。时间复杂度初看有点迷惑，外层循环遍历所有元素，内层还有一个while循环，直觉上像是O(n²)。但关键在这里：每个元素只会被后面的while循环“向后扩展”最多一次。为什么？因为你只从序列的起点开始扩展，而每个序列只有一个起点，也就是说，如果某一次 while 循环从数字 a 一直数到了 b，那 a+1、a+2、...、b-1 这些数都不会再成为任何一次 while 的起点，因为它们的前一个数都存在，它们不是起点。所以所有 while 循环总共走过的步数不会超过数组中元素的总数。外层遍历加上内层扩展，总的操作次数是O(n)。

提示：这个“每个元素最多被访问常数次”的论证方式，在复杂度分析里很常见。下次看到双重循环，先别急着喊O(n²)，想想内层循环的累计工作量是否被某种机制限制住了。

2.4 为什么内层while整体是O(n)：一次说透

这一点面试时经常被追问，我单独拿出来讲透。

很多人疑惑：外层遍历每个数字时，只要这个数字是起点，就会执行while。如果数组是 [1,2,3,...,n]，那1是起点，从1开始while要跑n-1步，但如果这时外层遍历还没结束，后面遍历到2、3、...、n的时候，因为2的前驱1存在、3的前驱2存在……它们都不是起点，所以不会进入while。整个流程只有1这一个起点，while总步数是n-1。

如果数组比较稀疏，比如 [1, 100, 2, 101, 3, 102]，那起点有1和100两个，它们分别在while里各跑几步，加起来还是不超过数组长度。更一般地，因为“每个非起点元素都会被某个起点序列覆盖”，所以所有while步数加起来，等价于把所有连续序列的长度求和，而这个总和分摊到每个元素头上最多一次，显然≤n。所以总复杂度是O(n)，这个结论可以放心讲给面试官听。

另外有个小细节：外层循环遍历的是 set 而不是原数组 nums。这一点其实两种写法的复杂度量级是一样的，但遍历 set 有个微小好处：如果原数组里有很多重复值，去重后集合更小，外层循环的迭代次数就少一些，当然这不改变O(n)的量级，只会略微影响常数。我习惯写成遍历 set，逻辑上更顺，也方便观察“起点”这一特性。

2.5 关于这道题的几个常见追问

面试中围绕128题，我遇到过这几类追问，提前准备一下：

第一个：如果数组里有负数，算法还有效吗？有效。HashSet 对值的正负没有限制，连续序列照样可以通过 abs 关系判断，while 循环同样工作。所以负数完全不是问题。

第二个：如果数组元素很大，比如上亿个数字，内存放不下怎么办？那就要考虑分布式或外部存储了，这不是这道题考察的重点。面试官问这个通常是想看你对空间复杂度的认知，你回答“哈希集合需要O(n)额外空间，内存受限时需要用外部排序或其他方案”就可以。

第三个：能不能只用O(1)的额外空间，且保证O(n)时间？严格来说不可能，因为你要在无序数组里快速知道某个值是否存在。不加哈希这类数据结构，查找至少要有遍历成本，所以空间换时间在这个场景下是必然选择。

第四个：排在后面问你“最长非降子序列”这类题目时，要注意区分。最长连续序列要求值是连续递增的等差数列式连续（x, x+1, x+2, ...），而最长非降子序列不要求值连续，只要求在原数组中的相对顺序，属于动态规划或贪心+二分的范畴，两者不是一个套路。面试时先把题目类型分清，再决定用哈希、双指针还是DP。

3. 11. 盛最多水的容器：双指针与贪心的正确性

3.1 题面回顾与暴力解法的天花板

题目是这样的：给定一个长度为 n 的整数数组 height，每个元素代表坐标轴上一个点的高度，数组下标代表 x 轴位置。选出两个柱子，使得它们与 x 轴共同构成的容器能容纳最多的水。也就是说，找两个下标 i 和 j（i < j），使得容器面积min(height[i], height[j]) * (j - i)最大。注意不能倾斜容器，且水的容量只由较矮的柱子和宽度决定。

暴力解法非常直观，双重循环枚举所有 i、j 组合，计算面积取最大值，时间复杂度O(n²)，当数组长度达到 10^5 量级时会直接超时。如果面试时没有思路，先把暴力解写出来说清楚，然后再讲怎么优化，这反而是加分项，因为面试官能看到你的代码基本功和问题分析路径。

3.2 双指针收敛逻辑：为什么永远移动矮的那一边

双指针解法的核心逻辑只有一条：每次计算当前 left 和 right 之间的面积，然后移动较矮的那一边。

假设height[left] < height[right]，那当前面积由左边这一根柱子决定。如果这时移动 right（较高的一边），会出现什么情况？宽度从 right - left 变成了 right - 1 - left 或者更小，而高度依然受限于 height[left]——因为左边界没动，右边界不管变得多高，短板还是左边界，高度不可能超过 height[left]。所以面积要么变小，要么不增。换句话说，移动较高的那边，无论后续怎么走，都不可能得到一个比当前更大的面积。

反过来，如果移动较矮的 left，虽然宽度减少，但左边界的高度有可能变大，短板有可能被抬升，面积就有了增长的可能。所以“始终移动较矮的那一边”是一个合理的贪心策略：它保留了所有可能产生更大面积的机会，同时排除了不可能产生更大面积的方向。

这里也可以用生活化类比来理解：一个木桶能装多少水，取决于最短的那块木板。你想让桶变大，要么把短板换长（移动矮边），要么把桶壁间距拉大（但间距已经在随着指针移动不断缩小，宽度只会越来越小）。唯一能做文章的就是换掉短板。

3.3 正确性证明：面试官必问的一环

能写出双指针代码的人不少，但能严谨证明“移动矮边不会漏掉最优解”的人不多。我把证明思路整理成三步，面试时可以按这个顺序讲。

第一步，假设最优解对应的两条柱子下标是 i* 和 j*，且 i* < j*。双指针算法从最左端 left=0 和最右端 right=n-1 开始，两个指针一定会逐渐向内移动。在这个过程中，只要 left 还没有超过 i*，right 还没有小于 j*，最优解对应的 i* 和 j* 就仍然在被当前指针区间覆盖的范围内。

第二步，关键问题在于：指针移动的过程中，会不会在某个时刻把 i* 或 j* 越过，导致最优解被排除？我们证明不会。以左指针为例，假设 left 已经移动到了 i*，此时 right 还在 j* 的右侧，我们比较 height[left] 和 height[right]。如果 height[left] <= height[right]，那么根据算法规则，移动的是 left，也就是 left 会越过 i* 继续向右，这看起来好像会把最优解丢掉。但是请注意：因为 height[left] 此时是两者中较矮的，而最优解的高度就是 height[i*]（因为 i* 是短板），那么对于任意处于 [i*, j*] 区间内的右边界来说，由 i* 和该右边界组成的水量都不可能超过 i* 和 j* 组成的水量，因为宽度更小或高度不变。所以即使左指针越过了 i*，也不会影响已经得到的最大值，因为最优解的值已经被计算过了。同样的论证适用于右指针一侧。

第三步，归纳下来，当左指针或右指针中的某一个第一次到达最优解边界时，另一个指针一定会在某个时刻到达另一个最优解边界，且在这个过程中，最优解的面积一定被计算过一次。因此，双指针算法一定不会漏掉最优解。

这套证明不需要背下来，理解“移动矮边时，以这条矮边为边界的所有可能面积已经被当前状态覆盖”这个核心就够用了。面试官真正想听到的，是你明白为什么这种看似盲目的贪心是完备的。

3.4 代码实现与复杂度

Java 实现非常短：

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

Python 版本：

class Solution: def maxArea(self, height: List[int]) -> int: left, right = 0, len(height) - 1 max_area = 0 while left < right: h = min(height[left], height[right]) w = right - left max_area = max(max_area, h * w) if height[left] < height[right]: left += 1 else: right -= 1 return max_area

时间复杂度O(n)，因为两个指针总共移动 n 次；空间复杂度O(1)，只用了两个下标变量。这里的边界条件要注意：当 height[left] == height[right] 时，移动哪一边都可以，本质原因是两边相等时移动任意一边都不会影响最优解的覆盖，你可以默认移动 right，也可以加一个left++分支，实测对结果没有影响，但代码里要写清楚分支，避免死循环。我习惯在相等时移动 left，写起来顺手，但逻辑上你写成移动 right 也完全没问题。

3.5 容易踩的坑与边界

这题虽然代码少，但有几处细节值得注意。

第一个坑是计算宽度时用的下标差。如果用right - left + 1，那就错了，因为容器是两个柱子之间夹的区间，宽度应该是 right - left。比如下标0和下标3之间，宽度是3，盛水面积是 min(h0, h3) * 3，而不是乘以4。这个错误很隐蔽，尤其是在你脑子想着“有几个间隔”时会算错。

第二个坑是最小高度取错了。面积要用Math.min(height[left], height[right])，这是短板效应，如果用Math.max去算，概念就反了。这个想象一下就能明白，水会从矮的那边溢出去。

第三个坑是数组长度为2的边界。比如 height = [1, 1]，初始 left=0，right=1，循环执行一次，面积1*1=1，返回1，没有问题。数组长度为1时，循环不执行，返回0，也是合理的，因为一根柱子不能盛水。

第四个坑是在 while 循环内部更新最大值的时机。有些同学会先把指针移动了再计算面积，这样容易导致漏掉初始两端的组合。正确的顺序是：先计算当前 left/right 下的面积并更新最大值，然后再移动指针。顺序反了虽然某些情况下结果碰巧一样，但逻辑上是有问题的。

4. 两道题的横向对比与思维迁移

4.1 优化路径的两种典型范式

做算法题久了会发现，数组类问题的优化路径大体就两类。

一类是“加缓存”。128题就是典型，把一个无序数组转换成哈希集合，把每次查找从线性扫描变成O(1)，从而让整体复杂度从O(n²)或O(n³)降到O(n)。类似的还有两数之和，也是用HashMap把配对查找变成O(1)；以及最长无重复子串，用哈希表记录字符最近出现位置，配合滑动窗口完成O(n)扫描。这类题目的共同点是：空间换时间，核心在于“重复查询”是否频繁。

另一类是“减搜索空间”。11题的精髓就是每走一步，就排除掉一大片不可能成为最优解的组合。很多看似O(n²)的组合枚举，通过一些单调性条件，可以把搜索空间从二维压缩成一维。最典型的迁移是“接雨水”（LeetCode 42题），也是双指针，从两边往中间收敛，每次处理较矮的一侧；还有三数之和，排序后用双指针把三重循环压成O(n²)。这类题目的核心是：当你能够证明某一部分组合“不可能更优”时，就可以大胆地把它从候选集里剔除。

这两个范式不是互斥的，很多难题是两者叠加。比如接雨水，既要理解高度积水的单调性质，又要用双指针维护左右两侧的状态。所以我把这两道题放在一起刷，目的就是让你在做题时先识别“这道题的瓶颈是重复查询，还是无效组合枚举”，然后对症下药。

4.2 从这两道题延伸出去的姊妹题

既然提到了迁移，我列一个简单的对照表，方便你继续刷：

看到没有，几乎所有数组题优化到最后，要么是在用哈希表降低单次查询成本，要么是在用某种规则缩小搜索范围。如果你能把128和11吃透，这些姊妹题的思路会顺很多。

4.3 面试时怎么讲这两道题

面试场景下，我建议按这个顺序组织你的回答。

先讲清楚暴力解法和它的复杂度，这不仅是为了展示基础，更是为了给后续优化提供一个对照的基准。比如128题，先说排序或者双重枚举，然后指出问题在于复杂度不满足要求。11题则说双重循环枚举所有柱对，O(n²)，在大数据量下不可行。

然后讲优化思路，一定要带“为什么”。128题讲“每个元素在哈希集合中查询O(1)，且只有序列起点才扩展，每个序列只被扫描一次”；11题讲“移动矮边，短板有希望变高，移动高边面积不可能超过当前值，因此不会漏解”。面试官最在意的就是你有没有这个推导过程。

最后主动给出复杂度分析，包括时间和空间，甚至可以把内层while的累计工作量单独解释一遍。我见过太多候选人只知道写代码，讲不清复杂度，这是非常明显的短板。把这篇文章里的论证思路顺一遍，面试基本能顶住追问。

5. 实战心得与避坑记录

5.1 我自己刷这两道题踩过的坑

128题我第一次写的时候就写出了一个隐藏的O(n²)。当时我的做法是，把数组全部放进HashSet后，对每个元素都往后 while 扩展一遍，没有判断 num-1 是否在集合中。数组 [1,2,3,...,10000] 这种情况下，从1数10000步，从2数9999步……虽然每个查询是O(1)，总步数加起来却是等差数列求和，足足 O(n²)。当时测试用例刚好有一个特别长的连续数组，直接超时。这个教训让我彻底记住了“起点判断”的重要性。

11题我踩过的坑是宽度计算。有一次写完代码，脑子一热把面积写成了Math.min(height[left], height[right]) * (right - left + 1)，结果在 height = [1, 2, 3, 4] 上算出了错答案，排查了半天才发现是多加了1。后来我给自己立了个规矩：涉及区间长度、下标差这类计算，一律先用具体的极短数组（比如长度2的数组）验算一遍再提交。

另一个11题的小经验：相等情况的处理。有朋友说过，如果height[left] == height[right]时随便移动哪边都行。理论上确实如此，但我实际测试中发现，如果两边相等的时候你写的是left++，在连续多个相等柱子的数组里，可能会多走一些重复计算。当然复杂度不变，结果也正确。我后来统一写成left++，顺手且稳定。

5.2 一个有意思的场景化组合验证

刷题不能只看单个解法，有时候把两道题的思想拼起来用，能加深理解。我拿一个场景举个例子：给定一个无序数组，要求找“数组中最长的连续上升段”。这里“连续”指下标连续，“上升”指值严格递增。

比如 [3, 1, 2, 4, 5, 7, 6]，最长的连续上升段是 [1, 2, 4, 5, 7]，长度5。如果暴力做，对于每个起点都要往后延伸，遇到下降就断开，最坏O(n²)，而且有大量重复扫描。那怎么优化？思考方式和128很像：让每个元素只被访问有限次。可以维护一个全局数组 dp，dp[i] 表示以 i 结尾的最长连续上升段长度，那么当 nums[i] > nums[i-1] 时 dp[i] = dp[i-1] + 1，否则重置为1。这个解法只用了一次遍历，每个元素处理一次，本质上是把“重复向后扩展”改成了“递推记录状态”。它不像128那样靠哈希集合，而是靠 DP 状态转移，但思路同源：避免重复劳动。

再结合11题的思路想：如果把数组改成环形，即首尾相接，要求环形数组上的最长连续上升段，该怎么处理？我当时的做法是复制数组接在后面，然后用同样的DP思路扫描两倍长度，最后把长度截断到不超过原数组长度。这种迁移训练多了，再遇到陌生的题目就不慌了。刷题其实就是在练这种“把旧范式套到新场景”的能力。

5.3 一个建议的刷题节奏

如果你正在准备面试，这两道题可以这样安排：第一天先把128题从暴力到优化完整走一遍，理解“空间换时间”和“起点判断”的复杂度分析，再手写三遍代码直到闭眼能写出来；第二天做11题，重点不是代码，而是把双指针正确性证明自己推一遍，最好能对着镜子或者朋友讲出来，因为面试是要说给别人听的。第三天把这两题和姊妹题一起刷，比如两数之和、接雨水，看看能不能复用你总结的思路。

我见过不少人的状态是“看了题解觉得懂了，过两天又忘了”。原因在于他们只是在看，没有把每一步的“为什么”内化成自己的推理链条。真正的掌握，是你能在下一次遇到类似场景时，自觉地想到“这个查询可以加缓存”“这个枚举可以用双指针收敛”。这两道题就是启动这种思维的钥匙。

最后聊一点我的个人体验。刷题这件事，最怕的就是陷入“背题”的循环。背得了一百道，背不了两百道，更重要的是每道题背后的思维模型。128和11这两道题，一个教你在无序的世界里用哈希表建立快速索引，一个教你在有序的收敛过程中大胆排除不可能。它们看似简单，其实是两种主要优化思想的最小完备示例。把这两道题吃透，比盲目刷二十道同类题都来得实在。如果让我给刷题顺序提个建议，那就是从这两道题开始，先把“空间换时间”和“缩减搜索空间”这两个底座打好，后面再遇到什么难题，你不会慌的。