尧图网页设计 
本文的网课内容学习自B站左程云老师的算法详解课程旨在对其中的知识进行整理和分享~网课链接算法讲解050【必备】双指针技巧与相关题目_哔哩哔哩_bilibili一.奇偶数字归位题目按奇偶排序数组 II算法原理整体思路双指针策略该算法使用双指针来解决问题。一个指针even用于指向偶数位置初始化为0另一个指针odd用于指向奇数位置初始化为1。通过双指针不断地交换元素使得偶数位置为偶数奇数位置为奇数。从数组末尾取元素调整算法每次从数组末尾取一个元素根据这个元素的奇偶性将其交换到合适的位置偶数元素交换到偶数位置奇数元素交换到奇数位置。具体步骤初始化确定数组的长度n nums.length。初始化两个指针odd 1用于指向奇数位置和even 0用于指向偶数位置。循环交换元素在for (int odd 1, even 0; odd n even n;)循环中首先检查数组末尾元素nums[n - 1]的奇偶性使用位运算(nums[n - 1]1)来判断如果结果为1则表示该元素为奇数。如果(nums[n - 1]1) 1元素为奇数调用swap函数将这个奇数元素与odd指针所指的奇数位置的元素进行交换即swap(nums, odd, n - 1)。然后将odd指针向后移动2个位置因为奇数位置之间间隔为2即odd 2。如果(nums[n - 1]1)! 1元素为偶数调用swap函数将这个偶数元素与even指针所指的偶数位置的元素进行交换即swap(nums, even, n - 1)。然后将even指针向后移动2个位置因为偶数位置之间间隔为2即even 2。最终结果当循环结束后数组nums中的元素已经按照要求排序即偶数位置为偶数奇数位置为奇数最后返回这个数组。代码实现// 按奇偶排序数组II // 给定一个非负整数数组 nums。nums 中一半整数是奇数 一半整数是偶数 // 对数组进行排序以便当 nums[i] 为奇数时i也是奇数 // 当 nums[i] 为偶数时 i 也是 偶数 // 你可以返回 任何满足上述条件的数组作为答案 // 测试链接 : https://leetcode.cn/problems/sort-array-by-parity-ii/ public class Code01_SortArrayByParityII { // 时间复杂度O(n)额外空间复杂度O(1) public static int[] sortArrayByParityII(int[] nums) { int n nums.length; for (int odd 1, even 0; odd n even n;) { if ((nums[n - 1] 1) 1) { swap(nums, odd, n - 1); odd 2; } else { swap(nums, even, n - 1); even 2; } } return nums; } public static void swap(int[] nums, int i, int j) { int tmp nums[i]; nums[i] nums[j]; nums[j] tmp; } }二.寻找重复数题目寻找重复数算法原理整体思路快慢指针的运用这个算法使用了快慢指针的技巧类似于检测链表是否有环的方法。我们将数组中的元素视为链表中的节点数组的下标作为指针。例如对于数组numsnums[i]可以看作是节点i的下一个节点。确定存在环由于数组中有n 1个整数且数字都在[1, n]范围内根据抽屉原理必然存在至少一个重复的数。这种重复会导致在按照上述规则构建的“链表”中出现环。具体步骤快慢指针相遇初始化首先慢指针slow初始化为nums[0]快指针fast初始化为nums[nums[0]]。移动指针在循环中慢指针slow每次移动一步即slow nums[slow]快指针fast每次移动两步即fast nums[nums[fast]]。当slow和fast相遇时此时它们在环内的某个节点相遇。这一过程类似于在一个有环的链表中快慢指针同时出发快指针最终会追上慢指针。找到环的入口即重复的数指针重置当快慢指针相遇后将快指针fast重置为0数组的起始下标。再次移动指针然后慢指针slow和快指针fast以相同的速度每次移动一步移动。当它们再次相遇时这个相遇的节点就是环的入口也就是数组中的重复数。这是因为从链表头到环入口的距离和从快慢指针相遇点到环入口的距离是相等的。代码实现// 寻找重复数 // 给定一个包含 n 1 个整数的数组 nums 其数字都在 [1, n] 范围内包括 1 和 n // 可知至少存在一个重复的整数。 // 假设 nums 只有 一个重复的整数 返回 这个重复的数 。 // 你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。 // 测试链接 : https://leetcode.cn/problems/find-the-duplicate-number/ public class Code02_FindTheDuplicateNumber { // 时间复杂度O(n)额外空间复杂度O(1) public static int findDuplicate(int[] nums) { if (nums null || nums.length 2) { return -1; } int slow nums[0]; int fast nums[nums[0]]; while (slow ! fast) { slow nums[slow]; fast nums[nums[fast]]; } // 相遇了快指针回开头 fast 0; while (slow ! fast) { fast nums[fast]; slow nums[slow]; } return slow; } }三.接雨水题目接雨水算法原理一、辅助数组解法trap1的原理计算左右最大高度数组左最大高度数组lmax首先初始化lmax[0]nums[0]。然后通过一个循环for (int i 1; i n; i)计算从左到右每个位置i左侧的最大值。对于每个ilmax[i]取lmax[i - 1]和nums[i]中的较大值。这意味着lmax数组中的每个元素lmax[i]都表示从0到i这个区间内的最大高度。右最大高度数组rmax首先初始化rmax[n - 1]nums[n - 1]。然后通过一个逆序循环for (int i n - 2; i 0; i--)计算从右到左每个位置i右侧的最大值。对于每个irmax[i]取rmax[i 1]和nums[i]中的较大值。这样rmax数组中的每个元素rmax[i]都表示从i到n - 1这个区间内的最大高度。计算接水量对于每个位置i1 i n - 2该位置能够接住的水量取决于其左侧最大高度lmax[i - 1]和右侧最大高度rmax[i 1]中的较小值减去自身高度nums[i]。如果这个差值大于0则表示可以接住水将其累加到总的接水量ans中。即ans Math.max(0, Math.min(lmax[i - 1], rmax[i 1]) - nums[i]);二、双指针解法trap2的原理初始化定义左指针l 1从数组的第二个元素开始右指针r nums.length - 2从数组的倒数第二个元素开始。初始化lmaxnums[0]表示当前左指针左侧的最大高度rmaxnums[nums.length - 1]表示当前右指针右侧的最大高度。初始化接水量ans 0。移动指针并计算接水量在while (l r)循环中如果lmax rmax对于左指针l位置能接住的水量为lmax - nums[l]如果这个值大于0将其累加到ans中。然后更新lmax为lmax和nums[l]中的较大值并且左指针l向右移动一位l。否则即lmaxrmax对于右指针r位置能接住的水量为rmax - nums[r]如果这个值大于0将其累加到ans中。然后更新rmax为rmax和nums[r]中的较大值并且右指针r向左移动一位r--。这个过程不断更新左右两侧的最大高度并且根据较小的那一侧最大高度来计算当前指针位置能够接住的水量直到左右指针相遇。代码实现// 接雨水 // 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水 // 测试链接 : https://leetcode.cn/problems/trapping-rain-water/ public class Code03_TrappingRainWater { // 辅助数组的解法不是最优解 // 时间复杂度O(n)额外空间复杂度O(n) // 提交时改名为trap public static int trap1(int[] nums) { int n nums.length; int[] lmax new int[n]; int[] rmax new int[n]; lmax[0] nums[0]; // 0~i范围上的最大值记录在lmax[i] for (int i 1; i n; i) { lmax[i] Math.max(lmax[i - 1], nums[i]); } rmax[n - 1] nums[n - 1]; // i~n-1范围上的最大值记录在rmax[i] for (int i n - 2; i 0; i--) { rmax[i] Math.max(rmax[i 1], nums[i]); } int ans 0; // x x // 0 1 2 3...n-2 n-1 for (int i 1; i n - 1; i) { ans Math.max(0, Math.min(lmax[i - 1], rmax[i 1]) - nums[i]); } return ans; } // 双指针的解法最优解 // 时间复杂度O(n)额外空间复杂度O(1) // 提交时改名为trap public static int trap2(int[] nums) { int l 1, r nums.length - 2, lmax nums[0], rmax nums[nums.length - 1]; int ans 0; while (l r) { if (lmax rmax) { ans Math.max(0, lmax - nums[l]); lmax Math.max(lmax, nums[l]); } else { ans Math.max(0, rmax - nums[r]); rmax Math.max(rmax, nums[r--]); } } return ans; } }四.救生艇题目救生艇算法原理整体思路排序的目的首先对数组people进行排序这是为了方便后续的配对操作。通过排序可以使得体重较轻的人在数组的左边体重较重的人在数组的右边。双指针的运用算法使用双指针l左指针初始指向数组的第一个元素和r右指针初始指向数组的最后一个元素来遍历数组。每次尝试将最轻的人和最重的人放在一艘船上如果他们的体重之和不超过limit如果不行则最重的人单独一艘船。具体步骤初始化对people数组排序后初始化变量ans 0用于记录所需的船的数量。l 0左指针指向数组的最左边。r people.length - 1右指针指向数组的最右边。sum 0用于临时存储两人的体重之和。循环配对或单独安排在while (l r)循环中首先计算当前指针所指两人的体重之和当l r时只有一个人就取这个人的体重即sum l r? people[l] : people[l]people[r];。如果sum limit说明最轻的人和最重的人不能放在同一艘船上此时最重的人右指针指向的人单独一艘船所以r--。如果sum limit说明最轻的人和最重的人可以放在同一艘船上此时l最轻的人已经安排r--最重的人已经安排。无论哪种情况都需要一艘船所以ans。最终结果当循环结束后即所有人都被安排到船上ans的值就是承载所有人所需的最小船数。代码实现import java.util.Arrays; // 救生艇 // 给定数组 people // people[i]表示第 i 个人的体重 船的数量不限每艘船可以承载的最大重量为 limit // 每艘船最多可同时载两人但条件是这些人的重量之和最多为 limit // 返回 承载所有人所需的最小船数 // 测试链接 : https://leetcode.cn/problems/boats-to-save-people/ public class Code04_BoatsToSavePeople { // 时间复杂度O(n * logn)因为有排序额外空间复杂度O(1) public static int numRescueBoats(int[] people, int limit) { Arrays.sort(people); int ans 0; int l 0; int r people.length - 1; int sum 0; while (l r) { sum l r ? people[l] : people[l] people[r]; if (sum limit) { r--; } else { l; r--; } ans; } return ans; } }五.盛最多水的容器题目盛最多水的容器算法原理整体思路双指针法的运用采用双指针法一个指针l指向数组的开头最左边的垂线另一个指针r指向数组的末尾最右边的垂线。通过移动指针来调整容器的宽度并根据指针所指元素的高度来计算容器的面积不断寻找最大面积。具体步骤初始化初始化变量ans 0用于存储最大的盛水面积。设定双指针l 0指向数组的第一个元素和r height.length - 1指向数组的最后一个元素。循环计算面积并调整指针在for (int l 0, r height.length - 1; l r;)循环中首先计算当前指针l和r所构成容器的面积计算公式为Math.min(height[l], height[r])*(r - l)。这里Math.min(height[l], height[r])表示容器的高度取两条垂线中较矮的高度(r - l)表示容器的宽度。然后将这个面积与当前的最大面积ans进行比较通过ans Math.max(ans, Math.min(height[l], height[r])*(r - l));更新最大面积。接着根据指针所指元素的高度来调整指针如果height[l] height[r]说明左边的垂线较矮将左指针l向右移动一位l这样做是因为如果保持右指针不变移动左指针可能会找到更高的垂线从而增大面积。如果height[l]height[r]说明右边的垂线较矮将右指针r向左移动一位r--同理这样做可能会找到更高的垂线从而增大面积。最终结果当循环结束即l不再小于r时ans的值就是能够盛最多水的容器的面积。代码实现// 盛最多水的容器 // 给定一个长度为 n 的整数数组 height 。有 n 条垂线第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。 // 找出其中的两条线使得它们与 x 轴共同构成的容器可以容纳最多的水 // 返回容器可以储存的最大水量 // 说明你不能倾斜容器 // 测试链接 : https://leetcode.cn/problems/container-with-most-water/ public class Code05_ContainerWithMostWater { // 时间复杂度O(n)额外空间复杂度O(1) public static int maxArea(int[] height) { int ans 0; for (int l 0, r height.length - 1; l r;) { ans Math.max(ans, Math.min(height[l], height[r]) * (r - l)); if (height[l] height[r]) { l; } else { r--; } } return ans; } }六.供暖器题目供暖器算法原理整体思路排序的重要性首先对房屋位置数组houses和供暖器位置数组heaters进行排序。排序后的数组便于我们进行后续的距离比较和最小加热半径的计算。遍历房屋寻找最小加热半径通过嵌套的循环结构遍历每一个房屋对于每个房屋找到能够为其供暖的最近的供暖器然后计算该房屋到这个供暖器的距离。最后取所有房屋到供暖器距离中的最大值作为最小加热半径。具体步骤初始化与排序初始化变量ans 0用于存储最终的最小加热半径。对houses数组和heaters数组分别进行排序这使得我们在后续计算距离时能够按照顺序进行高效的查找。遍历房屋外层循环使用for (int i 0, j 0; i houses.length; i)循环遍历每个房屋。其中i表示房屋的索引j表示供暖器的索引初始时都为0。对于每个房屋houses[i]我们需要找到能够为其供暖的最近的供暖器。寻找最近供暖器内层循环在内部的while (!best(houses, heaters, i, j))循环中通过不断调整供暖器的索引j来找到为houses[i]供暖的最优供暖器。函数best的作用是判断当前房屋houses[i]由当前供暖器heaters[j]供暖是否是最优的。如果j是最后一个供暖器j heaters.length - 1那么当前供暖器就是最优的否则比较当前供暖器heaters[j]到房屋houses[i]的距离Math.abs(heaters[j] - houses[i])和下一个供暖器heaters[j 1]到房屋houses[i]的距离Math.abs(heaters[j 1] - houses[i])如果前者小于后者那么当前供暖器就是最优的否则不是最优的需要继续寻找j。计算并更新最小加热半径当找到为houses[i]供暖的最优供暖器heaters[j]后计算房屋houses[i]到供暖器heaters[j]的距离Math.abs(heaters[j] - houses[i])并通过ans Math.max(ans, Math.abs(heaters[j] - houses[i]))更新最小加热半径ans。取所有房屋到供暖器距离中的最大值这样就可以确保所有房屋都能被供暖。最终结果当所有房屋都被遍历完后ans的值就是可以覆盖所有房屋的最小加热半径。代码实现public static int findRadius(int[] houses, int[] heaters) { Arrays.sort(houses); Arrays.sort(heaters); int ans 0; for (int i 0, j 0; i houses.length; i) { // i号房屋 // j号供暖器 while (!best(houses, heaters, i, j)) { j; } ans Math.max(ans, Math.abs(heaters[j] - houses[i])); } return ans; } // 这个函数含义 // 当前的地点houses[i]由heaters[j]来供暖是最优的吗 // 当前的地点houses[i]由heaters[j]来供暖产生的半径是a // 当前的地点houses[i]由heaters[j 1]来供暖产生的半径是b // 如果a b, 说明是最优供暖不应该跳下一个位置 // 如果a b, 说明不是最优应该跳下一个位置 public static boolean best(int[] houses, int[] heaters, int i, int j) { return j heaters.length - 1 || Math.abs(heaters[j] - houses[i]) Math.abs(heaters[j 1] - houses[i]); }七.缺失的第一个正数题目缺失的第一个正数算法原理整体思路区域划分与目标算法将数组划分为不同的区域。目标是让数组中索引为(i)的位置存放值(i 1)。有一个左边区域由指针(l)界定在这个区域左边是已经满足(arr[i]i 1)的部分有一个右边区域由指针(r)界定是所谓的“垃圾区”。通过交换调整元素位置算法通过不断地交换元素将合适的元素移动到合适的位置使得数组逐渐接近目标状态最后确定第一个缺失的正整数。具体步骤初始化初始化两个指针(l 0)它左边的区域是已经处理好的部分即索引(i)处的值为(i1)(r arr.length)它界定了右边的“垃圾区”。循环处理元素while (l r)情况一如果(arr[l]l 1)这意味着当前位置(l)已经满足要求直接将指针(l)向右移动一位(l)。情况二如果(arr[l]\leq l)这说明(arr[l])的值不应该出现在当前位置因为按照目标索引(l)处应该是(l 1)而(arr[l]\leq l)不符合要求如果(arr[l]r)表示(arr[l])的值超出了我们目前期望的范围我们期望(1)到(r)之间的值合理分布如果(arr[arr[l]-1]arr[l])说明有重复的值这三种情况都表明(arr[l])是一个“坏”元素将其与(r - 1)位置的元素交换并且将(r)减(1)即把这个元素扔到“垃圾区”。情况三如果不满足前面两种情况那么(arr[l])的值应该放在(arr[l]-1)的位置所以将(arr[l])与(arr[arr[l]-1])交换这样可以将(arr[l])放到更合适的位置。确定结果当循环结束后(l)左边的部分是满足要求的而第一个缺失的正整数就是(l 1)。代码实现// 缺失的第一个正数 // 给你一个未排序的整数数组 nums 请你找出其中没有出现的最小的正整数。 // 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。 // 测试链接 : https://leetcode.cn/problems/first-missing-positive/ public class Code07_FirstMissingPositive { // 时间复杂度O(n)额外空间复杂度O(1) public static int firstMissingPositive(int[] arr) { // l的左边都是做到i位置上放着i1的区域 // 永远盯着l位置的数字看看能不能扩充(l) int l 0; // [r....]垃圾区 // 最好的状况下认为1~r是可以收集全的每个数字收集1个不能有垃圾 // 有垃圾呢预期就会变差(r--) int r arr.length; while (l r) { if (arr[l] l 1) { l; } else if (arr[l] l || arr[l] r || arr[arr[l] - 1] arr[l]) { swap(arr, l, --r); } else { swap(arr, l, arr[l] - 1); } } return l 1; } public static void swap(int[] arr, int i, int j) { int tmp arr[i]; arr[i] arr[j]; arr[j] tmp; } }八.总结设置两个指针的技巧其实这种说法很宽泛1有时候所谓的双指针技巧就单纯是代码过程用双指针的形式表达出来而已没有单调性贪心方面的考虑。2有时候的双指针技巧包含单调性贪心方面的考虑牵扯到可能性的取舍。这对分析能力的要求会变高。其实是先有的思考和优化然后代码变成了双指针的形式。3所以双指针这个“皮”不重要分析题目单调性贪心方面的特征这个能力才重要。常见的双指针类型1同向双指针2快慢双指针3从两头往中间的双指针4其他 49.【必备】双指针技巧与相关题目
本文的网课内容学习自B站左程云老师的算法详解课程旨在对其中的知识进行整理和分享~网课链接算法讲解050【必备】双指针技巧与相关题目_哔哩哔哩_bilibili一.奇偶数字归位题目按奇偶排序数组 II算法原理整体思路双指针策略该算法使用双指针来解决问题。一个指针even用于指向偶数位置初始化为0另一个指针odd用于指向奇数位置初始化为1。通过双指针不断地交换元素使得偶数位置为偶数奇数位置为奇数。从数组末尾取元素调整算法每次从数组末尾取一个元素根据这个元素的奇偶性将其交换到合适的位置偶数元素交换到偶数位置奇数元素交换到奇数位置。具体步骤初始化确定数组的长度n nums.length。初始化两个指针odd 1用于指向奇数位置和even 0用于指向偶数位置。循环交换元素在for (int odd 1, even 0; odd n even n;)循环中首先检查数组末尾元素nums[n - 1]的奇偶性使用位运算(nums[n - 1]1)来判断如果结果为1则表示该元素为奇数。如果(nums[n - 1]1) 1元素为奇数调用swap函数将这个奇数元素与odd指针所指的奇数位置的元素进行交换即swap(nums, odd, n - 1)。然后将odd指针向后移动2个位置因为奇数位置之间间隔为2即odd 2。如果(nums[n - 1]1)! 1元素为偶数调用swap函数将这个偶数元素与even指针所指的偶数位置的元素进行交换即swap(nums, even, n - 1)。然后将even指针向后移动2个位置因为偶数位置之间间隔为2即even 2。最终结果当循环结束后数组nums中的元素已经按照要求排序即偶数位置为偶数奇数位置为奇数最后返回这个数组。代码实现// 按奇偶排序数组II // 给定一个非负整数数组 nums。nums 中一半整数是奇数 一半整数是偶数 // 对数组进行排序以便当 nums[i] 为奇数时i也是奇数 // 当 nums[i] 为偶数时 i 也是 偶数 // 你可以返回 任何满足上述条件的数组作为答案 // 测试链接 : https://leetcode.cn/problems/sort-array-by-parity-ii/ public class Code01_SortArrayByParityII { // 时间复杂度O(n)额外空间复杂度O(1) public static int[] sortArrayByParityII(int[] nums) { int n nums.length; for (int odd 1, even 0; odd n even n;) { if ((nums[n - 1] 1) 1) { swap(nums, odd, n - 1); odd 2; } else { swap(nums, even, n - 1); even 2; } } return nums; } public static void swap(int[] nums, int i, int j) { int tmp nums[i]; nums[i] nums[j]; nums[j] tmp; } }二.寻找重复数题目寻找重复数算法原理整体思路快慢指针的运用这个算法使用了快慢指针的技巧类似于检测链表是否有环的方法。我们将数组中的元素视为链表中的节点数组的下标作为指针。例如对于数组numsnums[i]可以看作是节点i的下一个节点。确定存在环由于数组中有n 1个整数且数字都在[1, n]范围内根据抽屉原理必然存在至少一个重复的数。这种重复会导致在按照上述规则构建的“链表”中出现环。具体步骤快慢指针相遇初始化首先慢指针slow初始化为nums[0]快指针fast初始化为nums[nums[0]]。移动指针在循环中慢指针slow每次移动一步即slow nums[slow]快指针fast每次移动两步即fast nums[nums[fast]]。当slow和fast相遇时此时它们在环内的某个节点相遇。这一过程类似于在一个有环的链表中快慢指针同时出发快指针最终会追上慢指针。找到环的入口即重复的数指针重置当快慢指针相遇后将快指针fast重置为0数组的起始下标。再次移动指针然后慢指针slow和快指针fast以相同的速度每次移动一步移动。当它们再次相遇时这个相遇的节点就是环的入口也就是数组中的重复数。这是因为从链表头到环入口的距离和从快慢指针相遇点到环入口的距离是相等的。代码实现// 寻找重复数 // 给定一个包含 n 1 个整数的数组 nums 其数字都在 [1, n] 范围内包括 1 和 n // 可知至少存在一个重复的整数。 // 假设 nums 只有 一个重复的整数 返回 这个重复的数 。 // 你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。 // 测试链接 : https://leetcode.cn/problems/find-the-duplicate-number/ public class Code02_FindTheDuplicateNumber { // 时间复杂度O(n)额外空间复杂度O(1) public static int findDuplicate(int[] nums) { if (nums null || nums.length 2) { return -1; } int slow nums[0]; int fast nums[nums[0]]; while (slow ! fast) { slow nums[slow]; fast nums[nums[fast]]; } // 相遇了快指针回开头 fast 0; while (slow ! fast) { fast nums[fast]; slow nums[slow]; } return slow; } }三.接雨水题目接雨水算法原理一、辅助数组解法trap1的原理计算左右最大高度数组左最大高度数组lmax首先初始化lmax[0]nums[0]。然后通过一个循环for (int i 1; i n; i)计算从左到右每个位置i左侧的最大值。对于每个ilmax[i]取lmax[i - 1]和nums[i]中的较大值。这意味着lmax数组中的每个元素lmax[i]都表示从0到i这个区间内的最大高度。右最大高度数组rmax首先初始化rmax[n - 1]nums[n - 1]。然后通过一个逆序循环for (int i n - 2; i 0; i--)计算从右到左每个位置i右侧的最大值。对于每个irmax[i]取rmax[i 1]和nums[i]中的较大值。这样rmax数组中的每个元素rmax[i]都表示从i到n - 1这个区间内的最大高度。计算接水量对于每个位置i1 i n - 2该位置能够接住的水量取决于其左侧最大高度lmax[i - 1]和右侧最大高度rmax[i 1]中的较小值减去自身高度nums[i]。如果这个差值大于0则表示可以接住水将其累加到总的接水量ans中。即ans Math.max(0, Math.min(lmax[i - 1], rmax[i 1]) - nums[i]);二、双指针解法trap2的原理初始化定义左指针l 1从数组的第二个元素开始右指针r nums.length - 2从数组的倒数第二个元素开始。初始化lmaxnums[0]表示当前左指针左侧的最大高度rmaxnums[nums.length - 1]表示当前右指针右侧的最大高度。初始化接水量ans 0。移动指针并计算接水量在while (l r)循环中如果lmax rmax对于左指针l位置能接住的水量为lmax - nums[l]如果这个值大于0将其累加到ans中。然后更新lmax为lmax和nums[l]中的较大值并且左指针l向右移动一位l。否则即lmaxrmax对于右指针r位置能接住的水量为rmax - nums[r]如果这个值大于0将其累加到ans中。然后更新rmax为rmax和nums[r]中的较大值并且右指针r向左移动一位r--。这个过程不断更新左右两侧的最大高度并且根据较小的那一侧最大高度来计算当前指针位置能够接住的水量直到左右指针相遇。代码实现// 接雨水 // 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水 // 测试链接 : https://leetcode.cn/problems/trapping-rain-water/ public class Code03_TrappingRainWater { // 辅助数组的解法不是最优解 // 时间复杂度O(n)额外空间复杂度O(n) // 提交时改名为trap public static int trap1(int[] nums) { int n nums.length; int[] lmax new int[n]; int[] rmax new int[n]; lmax[0] nums[0]; // 0~i范围上的最大值记录在lmax[i] for (int i 1; i n; i) { lmax[i] Math.max(lmax[i - 1], nums[i]); } rmax[n - 1] nums[n - 1]; // i~n-1范围上的最大值记录在rmax[i] for (int i n - 2; i 0; i--) { rmax[i] Math.max(rmax[i 1], nums[i]); } int ans 0; // x x // 0 1 2 3...n-2 n-1 for (int i 1; i n - 1; i) { ans Math.max(0, Math.min(lmax[i - 1], rmax[i 1]) - nums[i]); } return ans; } // 双指针的解法最优解 // 时间复杂度O(n)额外空间复杂度O(1) // 提交时改名为trap public static int trap2(int[] nums) { int l 1, r nums.length - 2, lmax nums[0], rmax nums[nums.length - 1]; int ans 0; while (l r) { if (lmax rmax) { ans Math.max(0, lmax - nums[l]); lmax Math.max(lmax, nums[l]); } else { ans Math.max(0, rmax - nums[r]); rmax Math.max(rmax, nums[r--]); } } return ans; } }四.救生艇题目救生艇算法原理整体思路排序的目的首先对数组people进行排序这是为了方便后续的配对操作。通过排序可以使得体重较轻的人在数组的左边体重较重的人在数组的右边。双指针的运用算法使用双指针l左指针初始指向数组的第一个元素和r右指针初始指向数组的最后一个元素来遍历数组。每次尝试将最轻的人和最重的人放在一艘船上如果他们的体重之和不超过limit如果不行则最重的人单独一艘船。具体步骤初始化对people数组排序后初始化变量ans 0用于记录所需的船的数量。l 0左指针指向数组的最左边。r people.length - 1右指针指向数组的最右边。sum 0用于临时存储两人的体重之和。循环配对或单独安排在while (l r)循环中首先计算当前指针所指两人的体重之和当l r时只有一个人就取这个人的体重即sum l r? people[l] : people[l]people[r];。如果sum limit说明最轻的人和最重的人不能放在同一艘船上此时最重的人右指针指向的人单独一艘船所以r--。如果sum limit说明最轻的人和最重的人可以放在同一艘船上此时l最轻的人已经安排r--最重的人已经安排。无论哪种情况都需要一艘船所以ans。最终结果当循环结束后即所有人都被安排到船上ans的值就是承载所有人所需的最小船数。代码实现import java.util.Arrays; // 救生艇 // 给定数组 people // people[i]表示第 i 个人的体重 船的数量不限每艘船可以承载的最大重量为 limit // 每艘船最多可同时载两人但条件是这些人的重量之和最多为 limit // 返回 承载所有人所需的最小船数 // 测试链接 : https://leetcode.cn/problems/boats-to-save-people/ public class Code04_BoatsToSavePeople { // 时间复杂度O(n * logn)因为有排序额外空间复杂度O(1) public static int numRescueBoats(int[] people, int limit) { Arrays.sort(people); int ans 0; int l 0; int r people.length - 1; int sum 0; while (l r) { sum l r ? people[l] : people[l] people[r]; if (sum limit) { r--; } else { l; r--; } ans; } return ans; } }五.盛最多水的容器题目盛最多水的容器算法原理整体思路双指针法的运用采用双指针法一个指针l指向数组的开头最左边的垂线另一个指针r指向数组的末尾最右边的垂线。通过移动指针来调整容器的宽度并根据指针所指元素的高度来计算容器的面积不断寻找最大面积。具体步骤初始化初始化变量ans 0用于存储最大的盛水面积。设定双指针l 0指向数组的第一个元素和r height.length - 1指向数组的最后一个元素。循环计算面积并调整指针在for (int l 0, r height.length - 1; l r;)循环中首先计算当前指针l和r所构成容器的面积计算公式为Math.min(height[l], height[r])*(r - l)。这里Math.min(height[l], height[r])表示容器的高度取两条垂线中较矮的高度(r - l)表示容器的宽度。然后将这个面积与当前的最大面积ans进行比较通过ans Math.max(ans, Math.min(height[l], height[r])*(r - l));更新最大面积。接着根据指针所指元素的高度来调整指针如果height[l] height[r]说明左边的垂线较矮将左指针l向右移动一位l这样做是因为如果保持右指针不变移动左指针可能会找到更高的垂线从而增大面积。如果height[l]height[r]说明右边的垂线较矮将右指针r向左移动一位r--同理这样做可能会找到更高的垂线从而增大面积。最终结果当循环结束即l不再小于r时ans的值就是能够盛最多水的容器的面积。代码实现// 盛最多水的容器 // 给定一个长度为 n 的整数数组 height 。有 n 条垂线第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。 // 找出其中的两条线使得它们与 x 轴共同构成的容器可以容纳最多的水 // 返回容器可以储存的最大水量 // 说明你不能倾斜容器 // 测试链接 : https://leetcode.cn/problems/container-with-most-water/ public class Code05_ContainerWithMostWater { // 时间复杂度O(n)额外空间复杂度O(1) public static int maxArea(int[] height) { int ans 0; for (int l 0, r height.length - 1; l r;) { ans Math.max(ans, Math.min(height[l], height[r]) * (r - l)); if (height[l] height[r]) { l; } else { r--; } } return ans; } }六.供暖器题目供暖器算法原理整体思路排序的重要性首先对房屋位置数组houses和供暖器位置数组heaters进行排序。排序后的数组便于我们进行后续的距离比较和最小加热半径的计算。遍历房屋寻找最小加热半径通过嵌套的循环结构遍历每一个房屋对于每个房屋找到能够为其供暖的最近的供暖器然后计算该房屋到这个供暖器的距离。最后取所有房屋到供暖器距离中的最大值作为最小加热半径。具体步骤初始化与排序初始化变量ans 0用于存储最终的最小加热半径。对houses数组和heaters数组分别进行排序这使得我们在后续计算距离时能够按照顺序进行高效的查找。遍历房屋外层循环使用for (int i 0, j 0; i houses.length; i)循环遍历每个房屋。其中i表示房屋的索引j表示供暖器的索引初始时都为0。对于每个房屋houses[i]我们需要找到能够为其供暖的最近的供暖器。寻找最近供暖器内层循环在内部的while (!best(houses, heaters, i, j))循环中通过不断调整供暖器的索引j来找到为houses[i]供暖的最优供暖器。函数best的作用是判断当前房屋houses[i]由当前供暖器heaters[j]供暖是否是最优的。如果j是最后一个供暖器j heaters.length - 1那么当前供暖器就是最优的否则比较当前供暖器heaters[j]到房屋houses[i]的距离Math.abs(heaters[j] - houses[i])和下一个供暖器heaters[j 1]到房屋houses[i]的距离Math.abs(heaters[j 1] - houses[i])如果前者小于后者那么当前供暖器就是最优的否则不是最优的需要继续寻找j。计算并更新最小加热半径当找到为houses[i]供暖的最优供暖器heaters[j]后计算房屋houses[i]到供暖器heaters[j]的距离Math.abs(heaters[j] - houses[i])并通过ans Math.max(ans, Math.abs(heaters[j] - houses[i]))更新最小加热半径ans。取所有房屋到供暖器距离中的最大值这样就可以确保所有房屋都能被供暖。最终结果当所有房屋都被遍历完后ans的值就是可以覆盖所有房屋的最小加热半径。代码实现public static int findRadius(int[] houses, int[] heaters) { Arrays.sort(houses); Arrays.sort(heaters); int ans 0; for (int i 0, j 0; i houses.length; i) { // i号房屋 // j号供暖器 while (!best(houses, heaters, i, j)) { j; } ans Math.max(ans, Math.abs(heaters[j] - houses[i])); } return ans; } // 这个函数含义 // 当前的地点houses[i]由heaters[j]来供暖是最优的吗 // 当前的地点houses[i]由heaters[j]来供暖产生的半径是a // 当前的地点houses[i]由heaters[j 1]来供暖产生的半径是b // 如果a b, 说明是最优供暖不应该跳下一个位置 // 如果a b, 说明不是最优应该跳下一个位置 public static boolean best(int[] houses, int[] heaters, int i, int j) { return j heaters.length - 1 || Math.abs(heaters[j] - houses[i]) Math.abs(heaters[j 1] - houses[i]); }七.缺失的第一个正数题目缺失的第一个正数算法原理整体思路区域划分与目标算法将数组划分为不同的区域。目标是让数组中索引为(i)的位置存放值(i 1)。有一个左边区域由指针(l)界定在这个区域左边是已经满足(arr[i]i 1)的部分有一个右边区域由指针(r)界定是所谓的“垃圾区”。通过交换调整元素位置算法通过不断地交换元素将合适的元素移动到合适的位置使得数组逐渐接近目标状态最后确定第一个缺失的正整数。具体步骤初始化初始化两个指针(l 0)它左边的区域是已经处理好的部分即索引(i)处的值为(i1)(r arr.length)它界定了右边的“垃圾区”。循环处理元素while (l r)情况一如果(arr[l]l 1)这意味着当前位置(l)已经满足要求直接将指针(l)向右移动一位(l)。情况二如果(arr[l]\leq l)这说明(arr[l])的值不应该出现在当前位置因为按照目标索引(l)处应该是(l 1)而(arr[l]\leq l)不符合要求如果(arr[l]r)表示(arr[l])的值超出了我们目前期望的范围我们期望(1)到(r)之间的值合理分布如果(arr[arr[l]-1]arr[l])说明有重复的值这三种情况都表明(arr[l])是一个“坏”元素将其与(r - 1)位置的元素交换并且将(r)减(1)即把这个元素扔到“垃圾区”。情况三如果不满足前面两种情况那么(arr[l])的值应该放在(arr[l]-1)的位置所以将(arr[l])与(arr[arr[l]-1])交换这样可以将(arr[l])放到更合适的位置。确定结果当循环结束后(l)左边的部分是满足要求的而第一个缺失的正整数就是(l 1)。代码实现// 缺失的第一个正数 // 给你一个未排序的整数数组 nums 请你找出其中没有出现的最小的正整数。 // 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。 // 测试链接 : https://leetcode.cn/problems/first-missing-positive/ public class Code07_FirstMissingPositive { // 时间复杂度O(n)额外空间复杂度O(1) public static int firstMissingPositive(int[] arr) { // l的左边都是做到i位置上放着i1的区域 // 永远盯着l位置的数字看看能不能扩充(l) int l 0; // [r....]垃圾区 // 最好的状况下认为1~r是可以收集全的每个数字收集1个不能有垃圾 // 有垃圾呢预期就会变差(r--) int r arr.length; while (l r) { if (arr[l] l 1) { l; } else if (arr[l] l || arr[l] r || arr[arr[l] - 1] arr[l]) { swap(arr, l, --r); } else { swap(arr, l, arr[l] - 1); } } return l 1; } public static void swap(int[] arr, int i, int j) { int tmp arr[i]; arr[i] arr[j]; arr[j] tmp; } }八.总结设置两个指针的技巧其实这种说法很宽泛1有时候所谓的双指针技巧就单纯是代码过程用双指针的形式表达出来而已没有单调性贪心方面的考虑。2有时候的双指针技巧包含单调性贪心方面的考虑牵扯到可能性的取舍。这对分析能力的要求会变高。其实是先有的思考和优化然后代码变成了双指针的形式。3所以双指针这个“皮”不重要分析题目单调性贪心方面的特征这个能力才重要。常见的双指针类型1同向双指针2快慢双指针3从两头往中间的双指针4其他