力扣100题-双指针

1.移动零

• 描述：给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

  请注意 ，必须在不复制数组的情况下原地对数组进行操作。

思路一：

• 从左到右遍历数组，发现非零数就按序重写到原数组中，再在数组的后半截补全对应的0，实现了不构建新数组
• 代码：

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        j = 0
        for i in range(n):
            if nums[i] != 0:
                nums[j] = nums[i]
                j += 1
        for i in range(j, n):
            nums[i] = 0

思路二：

• 有点神似快排，交换的条件是当前的数是非零的。左指针左边均是非零数，右指针到左指针为止皆是0(一般情况)
• 代码：

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        l = r = 0
        while r < n:
            if nums[r] != 0:
                nums[l],nums[r] = nums[r], nums[l] # 快速实现两个元素的交换
                l += 1
            r += 1
           

2.盛最多水的容器

• 描述：给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

  找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

  返回容器可以储存的最大水量。

  说明：你不能倾斜容器。

思路一：

• 贪心算法，左右指针分别从两端开始往中间靠，此时中间的任意的选择都是有可能。比较两个指针指向的数，选择高度较小的往中间走一步。
• ==证明==：从第一步开始假设，当前两个指针l, r直向左右两端，值分别是x, y,假设x<=y,距离为t，那么此时的结果就是min(x, y)*t = xt。假设左指针不动，此时右指针可以向左移动，不管怎么移动，其结果都是小于xt的，因为此时距离减少了，而min(x, y(new)) <= min(x, y) = x。因此所有以左指针为一端的结果都可以直接舍弃掉了，于是可以直接选择将左指针向右移动一步即可。
• 代码：

class Solution:
    def maxArea(self, height: List[int]) -> int:
        ans = 0
        n = len(height)
        l, r= 0, n-1
        while l < r:
            width = r-l
            if height[l] < height[r]:
                ans = max(ans, width*height[l])
                l += 1
            else:
                ans = max(ans, width*height[r])
                r -= 1
        return ans

3.三数之和：

• 描述：给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

  注意：答案中不可以包含重复的三元组。

思路一：

• 关键在于降低时间复杂度和重复的剪枝，暴力的做法就是三层循环O[N^3]。首先对数组进行排序，方便计算，在第二层和第三层循环使用双指针，不断向中间移动来寻找对应的target，这部分的时间复杂度就从O[N^2]降低到O[N]了。然后是在第一二层循环的时候都进行一下判重，找到并使用多个连续的重复数字的最后那一个。

• 代码：

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        n = len(nums)
        ans = list()
        
        for a in range(n-2):
            if a > 0 and nums[a] == nums[a-1]: # 跳过重复的数字
                continue
            c = n - 1
            target = -nums[a]
            for b in range(a+1, n-1):
                if b > a + 1 and nums[b] == nums[b-1]: #跳重
                    continue
                while b < c and nums[b] + nums[c] > target: #c的重复没有影响，当找到时会直接跳出
                    c -= 1
                if b == c:
                    break
                if nums[b] + nums[c] == target:
                    ans.append([nums[a], nums[b], nums[c]])
        return ans

4.接雨水：

• 描述：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

思路一：

• 动态规划，提前维护数组LeftMax和RightMax,对于每一个位置来说，它能接收的与水量为左右两边对应的最大值取较小值然后减去当前位置的高度。相当于求每个位置上的雨水高度然后累加
• 代码：

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        ans = 0

        leftMax = [height[0]] + [0]*(n - 1) # 数组连接来实现初始化
        rightMax = [0]*(n - 1) + [height[n - 1]]

        for i in range(1, n):
            leftMax[i] = max(leftMax[i-1], height[i]) # 从左往右更新
        for i in range(n-2, 0, -1):
            rightMax[i] = max(rightMax[i+1], height[i]) # 从右往左更新
        for i in range(1, n-1):
            ans += min(leftMax[i], rightMax[i]) - height[i]
        return ans

思路二：

• 单调栈，维护一个递减的序列，当遇到一个大于当前栈顶的值时，就出栈一个为top，然后将此时的栈顶和当前的值作为两端，top作为计算的位置。是以矩阵形式累加答案的，通过遍历一边数组就合计了所有的计算，很巧妙。
• 代码：

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        ans = 0
        stack = list() # 初始化栈

        for i, h in enumerate(height):
            while stack and h > height[stack[-1]]: # 只要栈非空或者出现了大于栈顶的数就不断执行
                top = stack.pop()
                if not stack: #一旦栈空了就退出
                    break
                left = stack[-1]
                curWidth = i - left - 1 # 对应的宽度
                curHeight = min(height[left], height[i]) - height[top] #对应的高度
                ans += curHeight*curWidth
            stack.append(i) # 无一例外地添加到栈中
        return ans

思路三:

• 双指针，是对思路一的优化，对于每个点，只需要知道它左右的最大值分别是多少即可，不需要把所有的值都计算出来，而这个需要的值可以在双指针移动的过程中得到。
• 代码：

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        ans = 0
        l, r = 0, n - 1
        leftMax = height[0]
        rightMax = height[n - 1]
        while l < r:
            leftMax = max(leftMax, height[l])
            rightMax = max(rightMax, height[r]) # 及时更新对应的两个左右最大值
            if height[l] < height[r]: # 相当于leftMax < rightMax, 对于l来说，左右两端的最大值的较小值就是leftMax
                ans += leftMax - height[l] 
                l += 1
            else:
                ans += rightMax - height[r]
                r -= 1
        
        return ans

小节：

• 双指针对于数组的操作更加灵活，比如移动零，可以对元素进行划分，也类似快速排序里的双指针
• 双指针+排序可以降低时间复杂度，把O[N^2]降为O[N]
• 双指针也可以是两个数组的简化，比如接雨水，作为重要的临时变量，按具体情况进行移动
• 更多在于元素之间的关系的体现，通过移动来实现一种筛选