双指针力扣题，如何巧妙运用提问？

双指针力扣题（leetcode） 5. 最长回文子串 难度：中等 相关标签：双指针、字符串、动态规划 题目： 给你一个字符串 s，找到 s 中最长的 回文子串。 示例 1: 输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。 示例 2: 输入：s = "cbbd" 输出："bb" 提示： \(1 <= s.length <= 1000\) \(s 仅由数字和英文字母组成\) 代码： class Solution { public: string longestPalindrome(string s) { int n = s.size(); if (n < 2) return s; // 空串/单字符直接返回 int max_len = 1; // 最长回文长度（至少1） int start = 0; // 最长回文的起始下标 // 第一步：枚举所有可能的子串 [left, right] for (int left = 0; left < n; left++) { // 优化1：提前剪枝——剩余字符数 < 当前最长，直接退出循环 if (n - left <= max_len) break; // 优化2：只枚举长度 > max_len 的子串（right从left+max_len开始） for (int right = left + max_len; right < n; right++) { // 第二步：双指针验证 [left, right] 是否是回文 int l = left; int r = right; bool is_pal = true; while (l < r) { if (s[l] != s[r]) { is_pal = false; break; // 提前终止验证 } l++; r--; } // 第三步：更新最长回文记录（不再break，继续找更长） if (is_pal) { max_len = right - left + 1; start = left; } } } return s.substr(start, max_len); } }; class Solution { public: string longestPalindrome(string s) { int n = s.size(); if (n < 2) return s; // 空串/单字符直接返回 int max_len = 1; // 最长回文长度（至少1） int start = 0; // 最长回文的起始下标 // 第一步：枚举所有可能的子串 [left, right] // left是子串起始，right是子串结束 for (int left = 0; left < n; left++) { for (int right = left; right < n; right++) { // 第二步：双指针验证 [left, right] 是否是回文 int l = left; // 左指针：从子串开头出发 int r = right; // 右指针：从子串结尾出发 bool is_pal = true; // 标记是否是回文 // 双指针向中间收缩，逐一对比字符 while (l < r) { if (s[l] != s[r])// 字符不相等，不是回文 { is_pal = false; break; } l++; // 左指针右移 r--; // 右指针左移 } // 第三步：如果是回文，且长度更长，更新记录 if (is_pal && (right - left + 1) > max_len) { max_len = right - left + 1; start = left; // 更新最长回文的起始位置 } } } // 截取最长回文子串（从start开始，长度max_len） return s.substr(start, max_len); } }; 解法 双指针方式 时间复杂度 优点 缺点 暴力枚举 + 双指针验证 两端向中间收缩 O(n³) 逻辑 100% 直观，易理解 效率低（n=1000 时略慢） 中心扩展法（双指针） 中心向两侧扩散 O(n²) 效率高，空间最优 需要理解 “回文中心” class Solution { public: // 核心双指针：从中心向外扩展，返回扩展后的回文长度 int expand(const string& s, int l, int r) { // 只要左右指针没越界，且字符相等，就继续往两边扩 while (l >= 0 && r < s.size() && s[l] == s[r]) { l--; r++; } // 循环停止时，s[l] != s[r]，实际长度是 (r-1) - (l+1) + 1 = r - l - 1 return r - l - 1; } string longestPalindrome(string s) { int n = s.size(); // 基础边界处理 if (n < 2) return s; int start = 0; // 记录最长回文串的起始位置 int max_len = 1; // 记录最长回文串的长度 for (int i = 0; i < n; i++) { // 每一个字符 i 都可以作为“中心”向两边扩展 // 1. 奇数长度扩展：中心是一个字符（如 "aba", 中心是 'b'） int len1 = expand(s, i, i); // 2. 偶数长度扩展：中心是两个字符之间的空隙（如 "abba", 中心是 "bb"） int len2 = expand(s, i, i + 1); // 取两种情况中最长的那一个 int cur_max = max(len1, len2); // 如果发现更长的，更新起始点和长度 if (cur_max > max_len) { max_len = cur_max; // 计算起始点的技巧：当前中心 i 减去 (长度-1)/2 start = i - (max_len - 1) / 2; } } return s.substr(start, max_len); } }; 相似题目 最短回文串困难 回文排列简单 回文对困难 最长回文子序列中等 回文子串中等 不重叠回文子字符串的最大数目困难 11. 盛最多水的容器 难度：中等 相关标签：贪心、数组、双指针 题目： 给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。 说明：你不能倾斜容器。 示例 1: 输入：[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 提示： \(n == height.length\) \(2 <= n <= 10^5\) \(0 <= height[i] <= 10^4\) 代码： class Solution { public: int maxArea(vector<int>& height) { int n = height.size(); int left = 0; // 左指针：初始在最左边 int right = n - 1; // 右指针：初始在最右边 int max_water = 0; // 记录最大盛水量 // 双指针向中间移动，直到相遇 while (left < right) { // 步骤1：计算当前容器的盛水量 int width = right - left;// 容器的宽度（指针间距） int min_height = min(height[left], height[right]);//容器的高度（由矮边决定） int cur_water = width * min_height;// 当前盛水量 // 步骤2：更新最大盛水量 max_water = max(max_water, cur_water); // 步骤3：移动指针（谁矮谁动） if (height[left] < height[right]) left++; // 左指针矮，右移 else right--; // 右指针矮（或相等），左移 } return max_water; } }; 相似题目 接雨水困难 礼盒的最大甜蜜度中等 打家劫舍 IV中等 15. 三数之和 难度：中等 相关标签：数组、双指针、排序 题目： 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。 注意：答案中不可以包含重复的三元组。 示例 1: 输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]] 解释： nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 示例 2: 输入：nums = [0,1,1] 输出：[] 解释：唯一可能的三元组和不为 0 。 示例 3: 输入：nums = [0,0,0] 输出：[[0,0,0]] 解释：唯一可能的三元组和为 0 提示： \(3 <= nums.length <= 3000\) \(-10^5 <= nums[i] <= 10^5\) 代码： class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> res; // 存储最终结果 int n = nums.size(); if (n < 3) return res; // 边界：元素不足3个，直接返回空 // 步骤1：排序数组（核心前提，方便双指针和去重） sort(nums.begin(), nums.end()); // 步骤2：遍历固定第一个数nums[i] for (int i = 0; i < n; i++) { // 剪枝1：排序后第一个数>0，三数之和不可能为0，直接退出 if (nums[i] > 0) break; // 去重1：跳过重复的nums[i]（避免重复的三元组） if (i > 0 && nums[i] == nums[i-1]) continue; // 步骤3：双指针初始化 int left = i + 1; // 左指针：i的下一个位置（避免重复使用i） int right = n - 1; // 右指针：数组末尾 // 双指针向中间移动 while (left < right) { int sum = nums[i] + nums[left] + nums[right]; if (sum == 0) // 找到和为0的三元组 { // 加入结果集 res.push_back({nums[i], nums[left], nums[right]}); // 去重2：跳过重复的nums[left] while (left < right && nums[left] == nums[left+1]) left++; // 去重3：跳过重复的nums[right] while (left < right && nums[right] == nums[right-1]) right--; // 双指针同时移动，找下一组可能的数 left++; right--; } else if (sum < 0) left++;// 和太小，左指针右移（增大数值） else right--;// 和太大，右指针左移（减小数值） } } return res; } }; 相似题目 两数之和简单 最接近的三数之和中等 四数之和中等 较小的三数之和中等 等差三元组的数目简单 元素和最小的山形三元组 I简单 元素和最小的山形三元组 II中等 31. 下一个排列 难度：中等 相关标签：数组、双指针 题目： 整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。 例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。 整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。 例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。 类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。 而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。 给你一个整数数组 nums ，找出 nums 的下一个排列。 必须 原地 修改，只允许使用额外常数空间。 示例 1: 输入：nums = [1,2,3] 输出：[1,3,2] 示例 2: 输入：nums = [3,2,1] 输出：[1,2,3] 示例 3: 输入：nums = [1,1,5] 输出：[1,5,1] 提示： \(0 <= nums.length <= 100\) \(0<= nums[i] <= 100\) 代码： class Solution { public: void nextPermutation(vector<int>& nums) { int n = nums.size(); if (n <= 1) return; // 边界：长度<=1，无需调整 // 步骤1：双指针找升序拐点（j为左指针，i为右指针） // 模板对应：j是左指针，i是右指针，维护「nums[j] < nums[i]」的性质 int i = n - 1,j = n - 2 ; while (j >= 0 && nums[j] >= nums[i]) // 修正：判断条件仍用nums[j] >= nums[i]（j是左，i是右） { j--; i--; // 同步移动：j左移，i左移 } // 步骤2：若找到拐点，双指针找最小更大值并交换 if (j >= 0) // 修正：判断拐点是否存在，用j（原i） { // 模板对应：k是右指针，j是左指针，check(k,j) = nums[k] > nums[j] int k = n - 1; while (nums[k] <= nums[j]) k--; swap(nums[j], nums[k]); } // 步骤3：双指针反转后缀（模板中「指向一个序列」的双指针） int l = i, r = n - 1; while (l < r) { swap(nums[l], nums[r]); l++; r--; } } }; 算法推导 如何得到这样的排列顺序？这是本文的重点。我们可以这样来分析： 我们希望下一个数 比当前数大，这样才满足 “下一个排列” 的定义。因此只需要 将后面的「大数」与前面的「小数」交换，就能得到一个更大的数。比如 123456，将 5 和 6 交换就能得到一个更大的数 123465。 我们还希望下一个数 增加的幅度尽可能的小，这样才满足“下一个排列与当前排列紧邻“的要求。为了满足这个要求，我们需要： 在 尽可能靠右的低位 进行交换，需要 从后向前 查找 将一个 尽可能小的「大数」 与前面的「小数」交换。比如 123465，下一个排列应该把 5 和 4 交换而不是把 6 和 4 交换 将「大数」换到前面后，需要将「大数」后面的所有数 重置为升序，升序排列就是最小的排列。以 123465 为例：首先按照上一步，交换 5 和 4，得到 123564；然后需要将 5 之后的数重置为升序，得到 123546。显然 123546 比 123564 更小，123546 就是 123465 的下一个排列 以上就是求 “下一个排列” 的分析过程。 算法过程 标准的 “下一个排列” 算法可以描述为： 从后向前 查找第一个 相邻升序 的元素对 \((j,i)\)，满足 \(nums[j] < nums[i]\)。此时 \([i,end)\) 必然是降序 在 \([i,end)\) 从后向前 查找第一个满足 \(nums[j] < nums[k]\) 的 \(k\)。\(nums[j]、nums[k]\) 分别就是上文所说的「小数」、「大数」 将 \(nums[j]\) 与 \(nums[k]\) 交换 可以断定这时 \([i,end)\) 必然是降序，逆置 \([i,end)\)，使其升序 如果在步骤 \(1\) 找不到符合的相邻元素对，说明当前 \([begin,end)\) 为一个降序顺序，则直接跳到步骤 \(4\) 该方法支持数据重复，且在 \(C++ STL\) 中被采用。 作者：Imageslr 链接：https://leetcode.cn/problems/next-permutation/solutions/80560/xia-yi-ge-pai-lie-suan-fa-xiang-jie-si-lu-tui-dao-/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 代码分析 先明确核心目标 「下一个排列」的本质是：找到比当前排列大的所有排列中，最小的那个；如果当前已经是最大排列（比如[3,2,1]），就返回最小排列（[1,2,3]）。 步骤 1：双指针找升序拐点（j 左指针，i 右指针） 核心逻辑 从数组末尾往前找，找到第一个「左数 < 右数」的位置（升序拐点）—— 这个拐点是「能让排列变大的最小突破口」。 代码逐句解释 int i = n - 1,j = n - 2 ; // i（右指针）指向最后一个数，j（左指针）指向倒数第二个数 while (j >= 0 && nums[j] >= nums[i]) { // 只要j没越界，且「左数 >= 右数」（降序） j--; // 左指针左移 i--; // 右指针左移 } 例子理解（以nums = [1,3,2]为例） 初始：i=2（值 2）、j=1（值 3）→ nums[j]=3 >= nums[i]=2（降序），进入循环； 循环后：i=1（值 3）、j=0（值 1）→ nums[j]=1 < nums[i]=3（升序），停止循环； 结论：找到拐点j=0（值 1），这个位置是「能变大的最小位置」。 为什么要找这个拐点？ 如果数组后缀全是降序（比如[1,3,2]的后缀[3,2]），说明这部分已经是「最大排列」，无法再变大；只有找到第一个升序对，才能通过「交换拐点和后缀里的数」让整体排列变大。 步骤 2：找后缀中最小的更大值，和拐点交换 核心逻辑 找到拐点j后，在j右侧的后缀里，找「比 nums [j] 大的所有数中最小的那个」（保证变大的幅度最小），和j交换 —— 这是「下一个排列」的关键：既要变大，又要变的幅度最小。 代码逐句解释 if (j >= 0) { // 如果找到拐点（j没越界，说明不是最大排列） int k = n - 1; // k从数组末尾开始找（后缀是降序，末尾是最小的数） while (nums[k] <= nums[j]) k--; // 找第一个「比nums[j]大」的数 swap(nums[j], nums[k]); // 交换，让排列变大，且幅度最小 } 例子理解（接上面nums = [1,3,2]） 拐点j=0（值 1），k 从末尾（k=2，值 2）开始找； nums[k]=2 > nums[j]=1，停止循环； 交换\(j=0\)和\(k=2\)，数组变为\([2,3,1]\)？❌ 纠正：原数组是\([1,3,2]\)，交换后是\([2,3,1]\)？不，原数组\([1,3,2]\)的拐点\(j=0(1)\)，\(k=2(2)\)，交换后是\([2,3,1]\)？（补充：如果是\(nums=[1,2,3]\)，拐点\(j=1\)（2），k=2（3），交换后是\([1,3,2]\)，这就是「下一个排列」）。 为什么从末尾找？ 因为\(j\)右侧的后缀是降序（步骤 1 找拐点的过程已经保证），所以从末尾往前找，第一个比\(nums[j]\)大的数，就是「最小的更大值」（比如后缀\([5,4,3]\)，找比 2 大的数，3 是最小的）。 步骤 3：反转拐点右侧的后缀 核心逻辑 交换后，\(j\)右侧的后缀还是降序（因为步骤 1 的降序没被破坏），反转这个后缀，让它变成升序 —— 这是为了保证「变大后的排列是最小的」（升序是后缀的最小排列）。 代码逐句解释 int l = i, r = n - 1; // l指向后缀的起始位置（步骤1结束后，i就是j+1） while (l < r) // 双指针向中间移动，反转后缀 { swap(nums[l], nums[r]); l++; r--; } 例子理解（接nums=[1,3,2]交换后的[2,3,1]） \(l=i=1\)（值 3），\(r=2\)（值 1）； 交换\(l=1\)和\(r=2\)，数组变为\([2,1,3]\)—— 这就是\([1,3,2]\)的下一个排列（验证：\([1,3,2]→[2,1,3]\)，是比它大的最小排列）。 为什么要反转？ 比如交换后后缀是\([3,1]\)（降序），反转后是\([1,3]\)（升序），这是该后缀的最小排列 —— 如果不反转，\([2,3,1]\)比\([2,1,3]\)大，不符合\(「下一个排列（最小的更大值）」\)的要求。 极端情况：当前是最大排列（比如[3,2,1]） \(步骤 1：j 会一直左移到 - 1(没找到拐点)，跳过步骤 2\)； 步骤 3：\(l=i=0，r=2\)，反转整个数组，得到\([1,2,3]\)（最小排列），符合题目要求。 三个步骤的核心逻辑总结 步骤 目标 本质 1. 找拐点 找到「能变大的最小位置」 打破后缀的降序，找到调整的突破口 2. 交换 让排列「刚好变大一点」 找最小的更大值，保证变大幅度最小 3. 反转 让变大后的排列「最小」 把后缀转为升序，得到最小排列 这三个步骤环环相扣，最终实现「找到比当前大的最小排列」的核心目标，且全程只用双指针，时间复杂度 O (n)，符合题目「原地修改、常数空间」的要求。 相似题目 第一个错误的版本简单 蜡烛之间的盘子中等 找出数组排序后的目标下标简单 42. 接雨水 难度：困难 相关标签：栈、数组、双指针、动态规划、单调栈 题目： 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 示例 1: 示例 2: 输入：nums = [3,1,3,4,2] 输出：3 示例 3: 输入：nums = [3,3,3,3,3] 输出：3 提示： \(0 <= nums.length <= 10^5\) \(-10^9 <= nums[i] <= 10^9\) \(nums\) 是一个非递减数组 \(-10^9 <= target <= 10^9\) 代码： class Solution { public: int trap(vector<int>& height) { int n = height.size(); if (n <= 2) return 0; // 边界：少于3根柱子，无法接水 // 双指针初始化：l=左指针（区间左边界），r=右指针（区间右边界） int l = 0, r = n - 1; int left_max = height[l], right_max = height[r]; int res = 0; // 总接水量 // 模板对应：遍历区间（l/r向中间移动，等价于模板中i遍历、j维护） while (l < r) { // 核心单调性：left_max < right_max → l位置的水量由left_max决定 if (left_max < right_max) { l++; // 左指针右移（对应模板中j移动） // 维护left_max（区间[0,l]的最大高度） left_max = max(left_max, height[l]); // 业务逻辑：计算当前l位置的接水量 res += left_max - height[l]; } else { r--; // 右指针左移（对应模板中i移动） // 维护right_max（区间[r,n-1]的最大高度） right_max = max(right_max, height[r]); // 业务逻辑：计算当前r位置的接水量 res += right_max - height[r]; } } return res; } }; 先考察一下，以这个情况为例子，第一个困惑，我们是竖着这样一条一条的算呢，还是横着一层一层的算呢？我们可以都试一下，先看一看竖着算。 第一层是可以装水的，因为两边都是墙；第二层也是可以装水的，因为两边都有高于2的墙，虽然不是紧挨着这个格子，但是装满水的时候，两边就是水墙，一样能 \(hold\) 住。 第三层就不行了，因为左边最高的墙是二高，光2的水就都漏光了，右边就算有个3也没有用。大家一定都听说过木桶原理，也就是最短的那块木板决定能装多少水。 所以结论来了，位置 \(i\) 的这个竖条里能装多少水，就要看它左边最高的墙和右边最高的墙，取这俩里面更矮的那一个，在这个图里就是粉色的那个墙，再用这个高度减去当前位置 \(i\)​ 的高度。 为啥要剪掉自己原本的高度？比如这里 \(i\)​ 等于三的时候，墙本身就有一格高水位，虽然最高能到二格，但是底下的第一格已经被墙占了，所以能装的水就是 2-1=1 这里我们给左边最高和右边最高分别起个名字，left_max 和 right_max。用 Python 写位置 i 的这条竖条里能装的水就是这样：先取 left_max 和 right_max 里面最小的那一个，如果这个值大于 height [i] 的话，用这个值减去 height [i]，不然的话就是零。 这里要注意一点，左右两边最高的墙不一定要紧贴着，隔得远远的，中间隔着一堆水或者一堆墙也没有关系，重要的就是 \(i\)​ 左右两边最高的那两个墙。 至此问题就变成了，怎样高效的求出每个位置的左右两边的最大值。如果你每次都从 i 出发往两边扫一遍，那时间复杂度就是\(O(n²)\)，面试肯定凉凉，因为你在不停的重复计算，没有利用到之前计算的结果，太浪费了。 所以换一个思路，既然我们同时要维护左边最大和右边最大，那就直接用双指针，一个从左往右走，一个从右往左走，边走边更新 \(left_{max}\) 和 \(right_{max}\)​，这样一共遍历一次就可以搞定。 所以我们这里一共需要四个变量：\(left\) 和 \(right\) 是指针负责移动，然后 \(left_{max}\) 和 \(right_{max}\)​ 负责记录到目前为止左右最大的墙的高度。 比如在同一个例子上，一开始 \(left\) 指着开头，\(right\)​ 指着结尾，最开始左边最大和右边最大都可以假想成零，因为两边是没有墙的。 接下来就是灵魂拷问，我们怎样一边移动指针，一边计算载水量呢？具体一点说，就是每次是动左边的指针还是动右边的指针呢？这里动哪个指针，就表示要算哪个指针所在的竖条的载水量，这就要看哪边可以算了。 比如现在这个情况，左边最大是二，右边最大是三，也就是说对于 \(left\) 指向的这一列来说，左边最高已经定死了是二了，之后不会改变了，即使右边以后蹦出了更高的墙，对于这个 \(left\) 来说，短板依然是现在左边的这个 \(left_{max}\)，也就是说现在我们已经知道它的上限了，所以现在可以直接算了。 反观右边 \(right\) 这列，我们知道 \(right_{max}=3\) 比 \(left_{max}=2\) 大，如果后面它的左侧遇到更高的墙，那就说明 right 的上限有可能被抬高到现在的 right_max 上，所以 right 的上限现在还不能决定，要放一放，一会儿再算。 至此我们就已经看出了规则：左边最大和右边最大，其中哪个更小，就说明那一边的短板已经可以确定了，所以就可以算那一列，而另一边大的那一边短板还不能确定，所以要放一放。 一句话小结，面试的时候我们就可以这样解释：看 \(left_{max}\) 和 \(right_{max}\)​，谁小就先算哪边，因为较小的那一边水位的上限已经出现了，所以我们可以算；较大的那一边还可能被未来更高的另一侧抬高上限，所以我们现在先不算。 算完了还要记得更新那一侧的最大 \(max\)，然后把指针往中心移动一步。这样整体的算法对于这个列表只扫一遍，时间复杂度就是 \(O(n)\)，而且我们只用了四个变量，也没有用列表，空间复杂度就是 \(O(1)\)，这就是这道题的最优解法。 如果两边最高都一样的话怎么办？这种情况其实两边都可以算，因为彼此的高度就是短板，水位就算之后某一侧冒出了更高的墙，对于当前的这两列来说，短板依然是现在的高度。 写代码的时候，为了简洁，可以把相等的情况并进一边，比如并到左边，就是这样：\(if left_max <= right_max\)​，然后继续。 还有一个细节就是终止条件要注意一下，我们这里用 while left <= right 作为终止条件，也就是说两个指针相遇、指向同一个墙的时候也要算一遍，确保我们的每一个竖条都有被算到。 总结一下这道题：我们先试了一下竖条的计算方式，然后发现位置 i 能装的水，取决于它两边最高的墙其中更矮的那一边的高度。所以问题就变成，对于每个位置 i 怎么能不浪费的算两边分别最高的墙。 这里就可以利用双指针，一个指最左，一个指最右，再来两个变量，一个记左边最大，一个记右边最大。怎么判断左右两边的指针哪边可以算呢？这就要比较左边最大和右边最大的大小，小的那一边表示指针位置 i 的瓶颈已经出现，可以算，而大的那一边还不行。也就是说算左边最大和右边最大之中更小的那一边，再把指针往中间挪一步，进入下一个循环，这也是面试官最满意的答案。 其实说了半天，如果我们能放松空间复杂度，接受 \(O(n)\) 的话，其实就能很简单的把每个位置 i 的两边最大求出来。怎么做？用两个列表存，空间换时间，先从左边扫一遍，求出每个位置的左边最大值，存到第一个列表里；再从右边扫一遍，求出每个位置的右边最大值，放到第二个列表里。最后把这两个列表对应的 \(i\)，根据刚才的水的公式算一遍，都加起来就 \(OK\) 了。 相似题目 盛最多水的容器中等 除了自身以外数组的乘积中等 接雨水 II困难 倒水中等 有序三元组中的最大值 II中等 75. 颜色分类 难度：中等 相关标签：数组、双指针、排序 题目： 给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。 我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 必须在不使用库内置的 sort 函数的情况下解决这个问题。 示例 1: 输入：nums = [2,0,2,1,1,0] 输出：[0,0,1,1,2,2] 示例 2: 输入：nums = [2,0,1] 输出：[0,1,2] 提示： \(n == nums.length\) \(1 <= n <= 300\) \(nums[i] 为 0、1或 2\) 代码： class Solution { public: void sortColors(vector<int>& nums) { int n = nums.size(); if (n <= 1) return; // 边界：长度<=1无需排序 // 指针初始化：l=左指针（0区间右边界），cur=当前指针（遍历用，对应模板i），r=右指针（2区间左边界） int l = 0, cur = 0, r = n - 1; // 模板对应：cur作为右指针遍历（替代for循环），l/r维护区间性质 while (cur <= r) { // 情况1：当前数是0 → 交换到0的区间，l和cur都右移（维护[0,l)全0） if (nums[cur] == 0) { if(nums[cur] != nums[l]) swap(nums[cur], nums[l]); l++; cur++; } // 情况2：当前数是1 → 属于中间区间，直接右移cur（维护[l,cur)全1） else if (nums[cur] == 1) cur++; else // 情况3：当前数是2 → 交换到2的区间，r左移（维护(r,n-1]全2） { if(nums[cur] != nums[r]) swap(nums[cur], nums[r]); r--; // 注意：cur不移动（交换过来的数可能是0/1，需要重新检查） } } } }; 相似题目 排序链表中等 摆动排序中等 摆动排序 II中等 分析过程 [581. 最短无序连续子数组] 难度：中等 相关标签：栈、贪心、数组、双指针、排序、单调栈 题目： 给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。 请你找出符合题意的 最短 子数组，并输出它的长度。 示例 1: 输入：nums = [2,6,4,8,10,9,15] 输出：5 解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。 示例 2: 输入：nums = [1,2,3,4] 输出：0 示例 3: 输入：nums = [1] 输出：0 提示： \(1 <= nums.length <= 10^4\) \(-10^5 <= nums[i] <= 10^5\) 进阶：你可以设计一个时间复杂度为 O(n) 的解决方案吗？ 代码： class Solution { public: int findUnsortedSubarray(vector<int>& nums) { int n = nums.size(); if (n <= 1) return 0; // 数组长度小于2时直接返回0 int left = 0, right = -1; // 初始化左右边界 int max_val = nums[0], min_val = nums[n-1]; // 从左到右遍历，维护最大值，更新右边界 for (int i = 1; i < n; ++i)//无序中段的最大值应该小于有序右段的所有元素 { /* **元素小于前面最大值的时候才可以更新边界**，最后一次更新边界就是那个元素小于前面 某个位置的值（这个值就是最大值），这个点右侧是升序的一定大于前面那个最大值，否则right 就又要更新 */ if (nums[i] < max_val) right = i; // 当前元素小于最大值，需要排序，更新右边界 else max_val = nums[i]; // 更新最大值 } // 从右到左遍历，维护最小值，更新左边界 for (int i = n - 2; i >= 0; --i) { /* **元素大于后缀最小值的时候才可以更新边界**，最后一次更新边界就是那个元素大于后缀中 某个位置的值（这个值就是最大值），这个点左侧是升序的一定小于后缀中那个最小值，否则left 就又要更新 */ if (nums[i] > min_val) left = i; // 当前元素大于最小值，需要排序，更新左边界 else min_val = nums[i]; // 更新最小值 } return right - left + 1; // 返回需要排序的子数组长度 } }; 相似题目 排序每个滑动窗口中最小的子数组中等 核心思想 将数组分为三段：有序左段、无序中段、有序右段 左边界确定：从右向左遍历，维护最小值 无序中段的最小值应该大于有序左段的所有元素 当遇到比当前最小值大的数时，更新左边界 右边界确定：从左向右遍历，维护最大值 无序中段的最大值应该小于有序右段的所有元素 当遇到比当前最大值小的数时，更新右边界 最终结果：[左边界, 右边界]即为需要排序的最短子数组 关键要点 双指针思想：分别从两端向中间遍历，利用单调性优化 时间复杂度：O(n)，空间复杂度：O(1) 本质：找到破坏数组有序性的最小区间，使得排序该区间后整个数组有序 这个解法巧妙地利用了数组的分段特性，通过维护最大值和最小值来确定无序子数组的边界，避免了排序等高时间复杂度操作。