2-3 数组双指针

小节	位置
2.3.1	对撞指针
2.3.2	快慢指针

2.3.1 对撞指针

所谓对撞指针，就是指的初始状态的两个指针一个在左，一个在右；终止条件为左指针等于右指针。

序号	题目	题解
①	LeetCode 167.两数之和II-输入有序数组	题解2.3.1.1
②	LeetCode 344.反转字符串	题解2.3.1.2
③	LeetCode 345.反转字符串中的元音字母	题解2.3.1.3
④	LeetCode 125.验证回文串	题解2.3.1.4
⑤	LCR 139.训练计划 I	题解2.3.1.5
⑥	LeetCode 881.救生艇	题解2.3.1.6
⑦	LeetCode 11.盛最多水的容器	题解2.3.1.7
⑧	LeetCode 611.有效三角形的个数	题解2.3.1.8
⑨	LeetCode 15.三数之和	题解2.3.1.9
⑩	LeetCode 16.最接近的三数之和	题解2.3.1.10
⑪	LeetCode 18.四数之和	题解2.3.1.11
⑫	LeetCode 977.有序数组的平方	题解2.3.1.12
⑬	LeetCode 75.颜色分类	题解2.3.1.13
⑭	LeetCode 42.接雨水	题解2.3.1.14
⑮	LeetCode 845.数组中的最长山脉	题解2.3.1.15
⑯	LeetCode 978.最长湍流子数组	题解2.3.1.16

2.3.1.1 两数之和II -输入有序数组

LeetCode 167.两数之和II-输入有序数组 | | 返回目录2.3.1

思路：数组已经有序，那可以从左右两侧向中间靠拢，逼近目标值。

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        N = len(numbers)
        L, R  =0, N-1
        while L < R:
            while L  <R and  numbers[L] +  numbers[R] <target:
                L += 1
            while L < R and numbers[L] +  numbers[R] > target:
                R -= 1
            if L< R and numbers[L] +  numbers[R] == target:
                return [L+1, R+1]
        return []

2.3.1.2 反转字符串

LeetCode 344.反转字符串 | | 返回目录2.3.1

思路：这个题是对撞双指针的代表题目，也可以用它来进行数组逆序。

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        L, R = 0, len(s)-1
        while L < R:
            s[L], s[R] = s[R], s[L]
            L += 1
            R -=1

2.3.1.3 反转字符串中的元音字母

LeetCode 345.反转字符串中的元音字母 | | 返回目录2.3.1

思路 1：先用哈希表记住元音字母原始的索引，然后按照索引逆序改变其对应位置的值。

'''思路1.使用哈希表'''
class Solution:
    def reverseVowels(self, s: str) -> str:
        ll = list(s)
        # from collections import defaultdict
        # dict_1 = defaultdict(str)
        # N = len(s)
        # for i in range(N):
        #     if ll[i] in 'aeiouAEIOU':
        #         dict_1[i] = ll[i]
        # 注释中的内容一行代码就可以写完
        dict_1 = dict((i,ch) for (i,ch) in enumerate(ll) if ch in 'aeiouAEIOU')
        list_key = sorted(list(dict_1.keys()))

        length = len(list_key)
        for i in range(length):
            ll[list_key[i]] =  dict_1[list_key[length-1-i]]

        return ''.join(ll)

思路2：使用双指针，可以借鉴 2.3.1.2-反转字符串那道题的思路；
只不过并不是直接反转，而是先要判断条件。

'''思路2. 使用双指针'''
class Solution:
    def reverseVowels(self, s: str) -> str:
        N = len(s)
        ll = list(s)
        L, R = 0, N-1
        while L < R:
            while L < R and ll[L] not in 'aeiouAEIOU':
                L += 1
            while L < R and ll[R] not in 'aeiouAEIOU':
                R -=1
            
            if L<R:
                ll[L], ll[R] = ll[R], ll[L]
                L +=1
                R -=1
        return ''.join(ll)

2.3.1.4 验证回文串

LeetCode 125.验证回文串 | | 返回目录2.3.1

思路：回文字符串就是以中心为对称的关系，而且题目中说明了只考虑小写字母和数字两种字符的情况，其他的就该跳过。
也是考虑使用对撞指针.

class Solution:
    def isPalindrome(self, s: str) -> bool:
        # 先将所有大写转成小写
        s = s.lower()
        # 初始化双指针
        L, R = 0, len(s)-1

        while L < R:
            while L < R and not s[L].isalnum():
                # 对于非字母数字字符, 直接不考虑, 直接移动指针
                L += 1
            while L < R and not s[R].isalnum():
                R -= 1
            
            if L < R:
                if s[L] == s[R]:
                    L += 1
                    R -= 1
                else:
                    # 如果发现不相等的情况，说明左右不对称
                    return False
        return True

2.3.1.5 调整数组顺序使奇数位于偶数前面

LCR 139.训练计划 I | | 返回目录2.3.1

思路：该题和上面【反转字符串中的元音字母】思路是一脉相承的；
这里反转的不是元音字符，而是奇数or偶数，只需将判断条件做修改就行；

class Solution:
    def exchange(self, nums: List[int]) -> List[int]:
        
        L, R = 0, len(nums)-1
        while L < R:
            while L < R and nums[L] % 2 == 1:
                # 题目要求奇数在前，所以如果是奇数，左指针就不用反转，直接指针把L指针右移
                L += 1
            while L < R and nums[R] % 2 == 0:
                # 题目要求偶数在后，所以如果是偶数，右指针就不用反转，直接指针把R指针左移
                R -=1
            # 前面两个循环执行完毕后，说明L遇到的是偶数，R遇到的是奇数，
            # 此时交换一下位置即可
            if L < R:
                nums[L], nums[R] = nums[R], nums[L]
                L += 1
                R -= 1

        return nums

2.3.1.6 救生艇

LeetCode 881.救生艇 || 返回目录2.3.1

思路：该题说一艘船最多载两人，就容易联想到双指针。一个指针代表一个人，两个指针指向元素的和就是两个人的重量之和。
只不过，这里有一个和之前的题目不同的点，那就是我们需要对数组先进行排序。
为什么呢？因为如果两个人挤一条船，那么按照生活常识，我们肯定是希望尝试一个最轻的和一个最重的进行搭配，尽可能的利用船的承载能力。
所以如果用双指针代表两个人，就需要一个是来自于轻的一组，一个是来自于重的一组，所以按照重量先排序，左侧的就是轻的，右侧的就是重的，就可以利用对撞双指针了。

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        # 先按照重量升序排序
        people.sort()

        L, R = 0, len(people)-1
        cnt = 0
        while L < R:
            # 如果重量超过限制，就先让重的人单独坐一条船走
            while L < R and people[L] + people[R] > limit:
                R -= 1
                cnt += 1
            # 如果重量不超限制, 就两个人一起走
            while L < R and people[L] + people[R] <= limit:
                R -= 1
                L += 1
                cnt += 1
            # 如果最后还剩下一个人，就让他坐一条船走
            if L == R:
                cnt += 1
        return cnt

2.3.1.7 盛水最多的容器

LeetCode 11.盛最多水的容器 | | 返回目录2.3.1

思路：双指针代表的是可以作为容器边界的所有位置的范围。在一开始，双指针指向数组的左右边界，表示数组中所有的位置都可以作为容器的边界，每次将 对应的数字较小的那个指针 往另一个指针的方向移动一个位置，就表示我们认为这个指针不可能再作为容器的边界了, 然后再比较当前装水容量和之前的装水容量, 看哪个更大即可。

因为水桶能装多少水，是最矮的那个边界决定的。
意思是，如果不移动最矮的边界，而移动另一侧较高的边界，它只能往中间移动，装水的容量是不可能变多的。
所以我们只好移动最矮的那个边界，看看移动它之后，是否能使得装水量变多。

class Solution:
    def maxArea(self, height: List[int]) -> int:

        L, R = 0, len(height)-1
        water = 0
        while L < R:
        # 两个边界碰到一起之前, 能够装水
            while L < R and height[L] <= height[R]:
                water = max(water, height[L]*(R-L))
                L += 1

            while L < R and height[L] > height[R]:
                water = max(water, height[R]*(R-L))
                R -= 1
        return water

2.3.1.8 有效三角形的个数

LeetCode 611.有效三角形的个数 | | 返回目录2.3.1

思路：假设三条边分别为a,b,c;则满足三角形的条件为任意两边之和都大于第三边；
如果知道a,b,c的大小关系，比如 a<=b<=c, 那么两小边之和大于长边就一定能形成三角形

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        N =len(nums)
        if N < 3:
            return 0

        # 先从大到小排序
        nums.sort(reverse=True)
        res = 0
        for i in range(0,N-2):
            # 当前 i 位置的数左为最长边 lng； 另外两个小边就在[i+1, N-1]区间找
            L, R = i+1, N-1
            while L<R:
                # 目标是期望 小边之和 > 长边，即 a+b > c
                # lng, mid, sht = nums[i], nums[L], nums[R]

                # 如果 mid + sht 不够大，说明sht应该增大，即R侧应该往左移一次，找一个更大的sht
                if nums[i] >= nums[L] + nums[R]:
                    R -= 1
                else: # lng < mid + sht
                    # 如果此时能满足条件, R位置充当最短边sht，则R左侧的更大的数更能成为sht
                    # 即从 L+1 ~ R位置的所有数都可以成为最短边 sht(使得mid + sht更大)
                    # 与mid (L位置的值)一起构造一对小边; sht可取的个数为  => R - L
                    res += R - L
                    # 计数完之后，再将 L 右移一位，即 mid 减小一点，
                    # 这样会使得 mid + sht变小
                    # 看变小后的和是否还能大于lng
                    L += 1
                    # 使用双指针的核心就在这里, L和R靠拢时, mid+sht 的值是在缩小的
                    # 但只要大于lng, L和R遍历的范围就能够满足条件
        return res

更简洁的 code 写法：

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        N = len(nums)
        if N < 3:
            return 0
        nums.sort(reverse=True)
        res = 0
        for i in range(0, N-2):
            large = nums[i]
            L, R = i+1, N-1
            while L < R:
                while L < R and nums[L] + nums[R] <= large:
                    R -= 1 # 如果两边之和小于等于长边, 就说明最小边应该增大
                if L < R:
                    res += R- L 
                L += 1
                # 由于L 增大后, 中边其实缩小了, 所以之前R右侧数字因比R位置还小, 所以更不满足条件
        return res

2.3.1.9 三数之和

LeetCode 15.三数之和 | | 返回目录2.3.1

思路：此题和三角形那道题一样，只不过条件变为 nums[i] + nums[j] + nums[k] == 0
难点在于不能出现重复的三元组。如果我们先排序的话，然后遍历数组时，每次都将遍历的值，作为三元组开头的值，如果一旦发现这个开头值和上一次的开头值一样，那就说明重复，应该跳过。

第一种代码写法

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        N = len(nums)
        nums.sort()
        res = []
        for i in range(0,N-2):
            # 如果三元组的开头值和上一次的开头值重复, 可能会出现重复三元组, 直接不考虑
            if i>0 and nums[i] == nums[i-1]:
                continue
            # 每一次都在剩余可选范围内，维护左右两个指针
            L, R = i+1, N-1
            while L<R:
                if nums[i] + nums[L] + nums[R] > 0:
                    # 如果三数之和大于0, 就减小最大的数
                    R -= 1
                elif nums[i] + nums[L] + nums[R] < 0:
                    # 如果三数之和小于0, 就增大中间数
                    L += 1
                else: # 此时遇到满足条件的三个数
                    if res and nums[i] == res[-1][0] and nums[L] == res[-1][1]:
                        # 若三个数中的前两个与之前的相同, 说明重复, 不添加进结果
                        # (因nums已经被排序过, 故重复的 L 一定会紧邻, 故可与rse[-1]进行比较)
                        L += 1
                        continue
                    else:
                        res.append([nums[i], nums[L], nums[R]])
                        R -= 1
                        L += 1
        return res

第二种代码写法

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:

        nums.sort() # 升序排列
        N = len(nums)
        res=[]
        for i in range(0, N-2):
            if i > 0 and nums[i] == nums[i-1]: 
                continue # 如果 三元组的第一个数字重复, 可以不用考虑
            if nums[i] > 0: break # 如果三元组的第一个数组都大于0, 由于已经升序排列, 所以数字之和必不为0
            
            L, R = i+1, N-1
            while L < R:
                if L > i+1 and nums[L] == nums[L-1]:
                    L += 1
                    continue # 如果在i不变的情况下，三元组的第二个数组重复，也可以不用考虑

                while L < R and nums[L] + nums[R] > -nums[i]: 
                    R -= 1 # 如果两数之和大于了目标值, 说明应该减小较大数
                if L < R and  nums[L] +  nums[R] == -nums[i]:
                    res.append([nums[i], nums[L], nums[R]])
                L += 1
                    # 因为 L 右移之后, 数字变大, 所以原来 R右侧更大的数字更不会满足条件了, R可以先不变
        return res

2.3.1.10 最接近的三数之和

LeetCode 16.最接近的三数之和 | | 返回目录2.3.1

思路：和上面的三数之和思路一样，这里可以不考虑重复问题。因为题目假定每组输入只存在恰好一个解。

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        N = len(nums)
        # 先将res初始化为一个极值
        res = float('inf')
        nums.sort()
        for i in range(0,N-2):
            L, R = i+1, N-1
            while L<R :
                if abs(nums[i]+nums[L]+nums[R] - target) < abs(res-target):
                    res = nums[i]+nums[L]+nums[R]

                if nums[i]+nums[L]+nums[R] < target:
                    # 三数和偏小, 试着增大, 以此靠近 target
                    L += 1
                elif nums[i]+nums[L]+nums[R] > target:
                    # 三数和偏大, 试着减小, 以此靠近 target
                    R -= 1
                else: # 如果出现相等的情况
                    # 那就是最接近target, 而且题目说唯一解, 可以直接返回了
                    return target
                
        return res

2.3.1.11 四数之和

LeetCode 18.四数之和 | | 返回目录2.3.1

思路：这就是升级版的三数之和问题，可以考虑多搞一层循环来直接套用三数之和的解答方式。

第一种代码写法

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:

        N = len(nums)
        nums.sort()
        res = []
        # 相比于三数之和问题，只是多加了一层循环嵌套而已
        for i in range(N-3):
            if i > 0 and nums[i] == nums[i-1]: continue
            for j in range(i+1, N-2):
                if j>i+1 and nums[j] == nums[j-1]: continue
                L, R = j+1, N-1
                while L < R:
                    if L >j+1 and nums[L] == nums[L-1]:
                        L +=1
                        continue
                    while L < R and nums[L] + nums[R] > target - nums[i] -nums[j]:
                        R -= 1
                    if L <R and nums[i] + nums[j] + nums[L] + nums[R] == target:
                        res.append([nums[i], nums[j], nums[L], nums[R]]) 
                    L += 1

        return res

2.3.1.12 有序数组的平方

LeetCode 977.有序数组的平方 | | 返回目录2.3.1

思路：要是直接对数组nums内的数进行平方，再排序，这个可能不太符合题目想考察的点。这个题目对于数字的操作其实就是模拟了 $y=x^2$ 这个函数，函数开口向上，对称轴为 $x=0$ , 所以对于数组中的数据，谁离0更远，谁平方后就更大。

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        '''
        暴力解法：
        res = [num**2 for num in nums]
        return sorted(res)
        '''
        N  = len(nums)
        res = [0] * N
        L, R, idx  = 0, N - 1, N-1
        while L <= R:
            while L<=R and abs(nums[L]) > abs(nums[R]):
                # 如果 L 位置的数更远，就将其平方结果装入 res数组的末尾
                res[idx] = nums[L]**2
                L += 1
                idx -=1
            while L<=R and abs(nums[L]) <= abs(nums[R]):
                # 如果 R 位置的数更远，就将其平方结果装入 res数组的末尾
                res[idx] = nums[R]**2
                R -=1
                idx -=1
        return res

2.3.1.13 颜色分类

LeetCode 75.颜色分类 | | 返回目录2.3.1

思路：该题的本质其实是荷兰国旗问题，或者说简化版本的。后面讲排序问题的时候，会专门讨论荷兰国旗问题。

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        '''荷兰国旗问题'''
        N = len(nums)
        L, R = -1, N
        i = L+1
        while i < R:
            if L < R and nums[i] < 1:
                nums[i], nums[L+1] = nums[L+1], nums[i]
                L+=1
                i+=1
            elif L < R and nums[i] == 1:
                i+=1
            else:
                nums[i], nums[R-1] = nums[R-1], nums[i]
                R -=1

2.3.1.14 接雨水

LeetCode 42.接雨水 | | 返回目录2.3.1

思路 1：暴力解法，计算每个位置上的最高左右边界，得到每个位置装”水柱”的大小，但是会超出时间限制。

class Solution:
    def trap(self, height: List[int]) -> int:
        
        # 1.暴力解法
        # 计算每个位置上的"水柱"的大小
        # 注意，该方案超出时间限制，只是作为一个引子
        
        L_max, R_max = 0, 0
        N = len(height)
        water = []
        for i in range(1,N-1):
            # 对每一个位置，找其左、右两侧最高的边界
            # max 方法的时间复杂度是O(N)
            L_max = max(height[0:i])
            R_max = max(height[i+1:N])
            # 只有左右两侧存在比当前还要高的边界，才能装水，不然水就流走了
            if L_max > height[i] and R_max > height[i]:
                # 木桶能装水量是由短板决定的
                H = min(L_max, R_max)
                water.append(H-height[i])
        # 整个函数的时间复杂度是O(N^2), 会有测试用例时间超限
        return sum(water)

思路 2：在思路1的基础上进行改进。
思路1的想法是没问题的，能够跑通大部分用例，但是对于很长的height数组会超出时间限制。
如果能够将：【对每一个位置寻找其左右最高边界】这个操作的时间复杂度降下来，
那么就能够让整个函数的时间复杂度降低，所以很容易想到 “以空间换时间”。

如果从左往右遍历，要找左侧最高边界，就是在被遍历过的数中找，若能够将左侧遍历过的数中最高的边界，记录下来，那么每一次都只需将原来的左侧最高边界，与新遍历到的数进行对比，即：

对于 i 位置： L_max = max(L_max, height[i-1])

对于右侧的最高边界，就也同理，从右往左遍历，即可得到：

对于 j 位置， R_max = max(R_max, height[j+1])

这样，就能先遍历一道数组，将这些值记录在辅助数组中，时间复杂度O(N);
再遍历一道，计算装水量，还是O(N)的时间复杂度；所以总体的时间复杂度就是O(N)+O(N), 还是 O(N)
对于空间复杂度，额外使用了两个数组 L_max，R_max 来存放各个位置的左右边界，勉强也算是 O(2N) -> O(N)

class Solution:
    def trap(self, height: List[int]) -> int:
        
        '''思路2 “以空间换时间” '''
        N = len(height)
        # 最左和最右的柱子只能当边界，无法装水
        # 柱子一定要至少有3个才能装水
        water = 0
        if N <3:
            return water
        L_max, R_max = height[0], height[N-1]        
        L_boder, R_boder = [L_max]*N, [R_max]*N
        
        for L in range(1,N-1):
            # 将各个位置对应的左右最高边界分别存储到辅助数组中
            L_boder[L] = max(L_boder[L-1], height[L])
            R = N-1-L
            R_boder[R] = max(height[R], R_boder[R+1])

        for i in range(1,N-1):
            # 水柱高度由较矮边界决定：H = min(L_boder[i], R_boder[i])
            # 同时边界值还要比当前柱子本身要高才行：max(H-height[i], 0)
            water += max( min(L_boder[i], R_boder[i]) - height[i], 0)
        return water

思路 3：思路 2 的改进，能够跑通全部测试用例，但是用到了两个辅助数组，增加了空间复杂度。那么是否还有优化空间呢？

若在寻找左/右最高边界之时，直接计算装水量，岂不是可以不用辅助数组来存储数据了？
但是对于遍历到的数字，我们只能完全肯定其一边的最高边界。

比如【 从左往右遍历时,考察的是 L 位置】, 可以肯定 L_max 一定是 L 左侧最高边界：
此时 R_max 是 R 右侧的最高边界，并不一定是 L 右侧的最高边界
但是 R_max 它是不是 L位置的右侧最高边界重要吗？来讨论一下

情况1. if R_max > L_max, then H = L_max, 即 H 取值和 R_max 无关，原因如下：
如果 L~R 之间，还有更高的边界可以作为L的右边界，那 L_max 依旧是更矮的，不影响 H 取值是 L_max
如果 L~R 之间，不存在更高的边界，那 R_max 就是 L 的最高右边界,哪怕 L~R区间都是更矮的也不影响，反正有 R_max 作为右边界兜底，故 H 取值还是更矮的 L_max

情况2.if L_max > R_max, 那么确实就不好说了：
如果 L~R 之间存在更高的边界，那么就应该判断其与 L_max 的大小关系，
但是我们暂时无法找到这个值，无法确定更适合 L 位置的右边界
如果 L~R 之间，不存在更高的边界,那 R_max 就是 L 的最高右边界, H=min(L_max, R_max)=R_max
主要问题在于，我们暂时无法获取 L~R之间的数字的信息，因为尚未遍历到

但是反其道而行之！！！对于当前条件：L_max > R_max，无法判断 L 位置的 H 取值。但是却可以判断 R 位置的 H 取值！这正是我们讨论【从左往右遍历时,考察的是 L 位置】时的情况1
如果我们现在【从 右往左遍历 时,考察的是 R 位置】，那么

L_max > R_max 这个情况
就是 R 位置的情况1：此时 R 位置的 H = R_max

对于 R 位置的情况2：条件是 R_max > L_max，同理，无法确定 L~R 之间是否有更适合作为 R 位置左边界的值
但是，它又转换成了对于 L 位置的情况1.

对于 R_max == L_max 的情况:
如果考察的是 L 位置，H 仍然能取 L_max
如果考察的是 R 位置，H 仍然能取 R_max。
仍然按照两个位置情况1的思路去理解
在写代码时，只需要将这种情况固定划分到考察 L 或者 R 的一种之中去就行
这样整个思路就能串通起来了,
由于只需要遍历一次数组，时间复杂度 O(N),
只有有限个辅助变量，空间复杂度O(1)。

class Solution:
    def trap(self, height: List[int]) -> int:
        N = len(height)
        # 最左和最右的柱子只能当边界，无法装水
        # 柱子一定要至少有3个才能装水
        water = 0
        if N <3:
            return water

        L_max, R_max = height[0], height[N-1]
        L, R = 1, N-2
        while L <= R :
            if L_max <= R_max:
                # 这是 从左往右遍历的 L 位置的情况1:H = L_max
                L_max = max(L_max, height[L])
                water += L_max - height[L]
                L += 1
            else:
                # 这是 从右往左遍历的 r 位置的情况1: H = R_max
                R_max = max(R_max, height[R])
                water += R_max - height[R]
                R -= 1
        return water

2.3.1.15 数组中的最长山脉

LeetCode 845.数组中的最长山脉 | | 返回目录2.3.1

思路：这个其实不是对撞指针了，是对每个位置展开一个左右指针，来对每个位置求山脉宽度。
其实可以理解为对撞指针的逆过程，从中间开始往两边扩散两个指针。

class Solution:
    def longestMountain(self, arr: List[int]) -> int:
        N = len(arr)
        width = 0
        i = 1
        while i < N-1:
            L, R = i-1, i+1
            # 先判断是否满足左右都下降的趋势
            if arr[i] >arr[L] and arr[i] >arr[R]:
                while L> 0 and arr[L-1] < arr[L]:
                    # L 一直尽可能地往左延伸
                    L -= 1
                while R< N-1 and arr[R+1] < arr[R]:
                    # R 一直尽可能的往右延伸
                    R += 1
                width = max(width, R-L+1)
            i = R # 如果之前存在山，那么就是(L,i,R)这一段, 所以 i 到 R 之间是下降趋势
        return width

2.3.1.16 最长湍流子数组

LeetCode 978.最长湍流子数组 | | 返回目录2.3.1

思路：其实这个题最好的解法不是使用这种扩散指针，但是确实可以参考上面 数组中的最长山脉 的思路来做。
这里只是提供一种解法，拓展思路，但确实code比较复杂，看起来也不太容易懂，可以看着玩玩。
更好的解法还是建议看下面快慢指针部分 2.3.2.7题解，该题的code。

class Solution:
    def maxTurbulenceSize(self, arr: List[int]) -> int:
        '''
        首先要搞清楚湍流是什么情况：
        ···< arr[M-2] > arr[M-1] < arr[M] > arr[M+1] < arr[M+2] > ···
                                    或者
        ···> arr[M-2] < arr[M-1] > arr[M] < arr[M+1] > arr[M+2] < ···
        '''
        # 按照 数组中的最长山脉 的题解思路来做， 特殊情况和边界情况的判断稍显复杂
        N = len(arr)
        width = 1
        if N == 1:   
            return width
        i = 0
        while i < N:
            if i == 0 or i == N-1:
            # 端点值先特殊讨论
                if (arr[0] != arr[1]) or (arr[N-2] != arr[N-1]): 
                    # 只要端点值的相邻值和它不相等, 就一定是一个宽度为2的湍流
                    width = max(2, width)
                i += 1
            # 第 1 种 湍流模式, M 点是邻域极大值
            elif arr[i-1] < arr[i] and arr[i] > arr[i+1]:
                # 这里的两个 flag是用来控制 < 或 > 符号的, 利用 -1 的不断自乘来实现转向
                flag_L, flag_R, left, right = -1, -1, i-1, i+1
                while left > 0 and (arr[left] - arr[left-1])* flag_L > 0:
                    left -= 1
                    flag_L *= -1  
                while right < N-1 and (arr[right] - arr[right+1])* flag_R > 0:
                    right += 1
                    flag_R *= -1
                width = max(width, right-left+1)
                i = right

            # 第 2 种 湍流模式, M 点是邻域极小值
            elif arr[i-1] > arr[i] and arr[i] < arr[i+1]:
                # 这里的两个 flag是用来控制 < 或 > 符号的, 利用 -1 的不断自乘来实现转向
                flag_L, flag_R, left, right = -1, -1, i-1, i+1
                while left > 0 and (arr[left] - arr[left-1])* flag_L < 0:
                    left -= 1
                    flag_L *= -1  
                while right < N-1 and (arr[right] - arr[right+1])* flag_R < 0:
                    right += 1
                    flag_R *= -1
                width = max(width, right-left+1)
                i = right 

            else:
                i += 1

        return width
        '''
        这种代码写法的核心思路就是借鉴的 最长山脉那道题，难点在于:
        1. 小于/大于符号在不断的交替, 这里是利用 -1 的自乘实现
        2. 数组左右端点值的特殊情况容易忽略
        总之这种代码写法稍微有点困难，也是因为刚刚才做完 最长山脉的题目，
        陷入了 定式思维 的陷阱, 才写出了这种方法。
        等下面用快慢指针的思路, 代码就更容易理解
        '''

2.3.2 快慢指针

所谓快慢指针，就是指的两个指针的移动频率不同，其中快指针因为某个条件，总是跑在慢指针更右侧。
通常终止条件就是快指针遍历完了数组。

序号	题目	题解
①	LeetCode 26.删除有序数组中的重复项	题解2.3.2.1
②	LeetCode 443.压缩字符串	题解2.3.2.2
③	LeetCode 80.删除有序数组中的重复项II	题解2.3.2.3
④	LeetCode 27.移除元素	题解2.3.2.4
⑤	LeetCode 283.移动零	题解2.3.2.5
⑥	LeetCode 334.递增的三元子序列	题解2.3.2.6
⑦	LeetCode 978.最长湍流子数组	题解2.3.2.7
⑧	LeetCode 485.最大连续 1 的个数	题解2.3.2.8

2.3.2.1 删除有序数组中的重复项

LeetCode 26.删除有序数组中的重复项 | | 返回目录2.3.2

思路：用快慢指针，快指针先去右侧看是否重复，慢指针用来修改原数组（维护去重部分的边界）

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        N = len(nums)
        if N <2:
            return N
        '''方案一. 遍历到的重复的数, 先跳过，将重复区域的最后一个数, 加入唯一元素区域'''
        s, f = 0, 1
        # 慢指针代表筛选出的【唯一元素区域】的右边界, 一开始这个区域是空的, 所以s=0 
        # 快指针代表后续待比较区域的元素, 因为至少要有2个元素才能比较是否重复, 所以f从第2个元素开始,f=1
        while f <= N:
            if f== N or nums[f] != nums[f-1] :
                # f位置的数与 f-1不相同, 说明：
                # f-1位置是某段重复区域的最后一个数了, f是新区域的第一个数.
                # 把f-1加进唯一元素区域
                nums[s] = nums[f-1]
                # 这个if条件里面之所以有 f==N 这个情况, 是因为f=N时, nums取不到值, 
                # 且nums的最后一个数N-1位置一定可以加入唯一区域, 因为这个数一定是某段区域的最后一个数(不管这段区域是否重复)
                # 同时不要忘记 右边界s向右扩张1位
                s += 1
            f += 1
        return s # s是右边界, 即唯一元素区域实际是 0 ~ s-1, 共 s 个元素

        '''
        # 方案二： 
        # 上面的方案都是将重复区域的最后一个元素更新到s位置
        # 这里是将重复区域的第一个元素更新到s位置
        s, f = -1, 0
        while f < N:
            # 这里的更新过程非常像在维护一个虚拟的栈
            # 当栈为空 s==-1，或者f遇到的数不等于栈顶元素 nums[f] != nums[s]
            # 就将栈的区域扩大一个：s+=1， 然后将f对应的元素入栈:nums[s] = nums[f]
            if s==-1 or nums[f] != nums[s]:
                s += 1
                nums[s] = nums[f]
            f += 1
        # 虚拟栈的范围是 0 ~ s, 共 s+1 个元素       
        return s+1

        # 用虚拟栈的思路会十分容易理解, 代码也很好写, 所以更推荐方案二
        '''

2.3.2.2 压缩字符串

LeetCode 443.压缩字符串 | | 返回目录2.3.2

思路：题目中说到只能使用常量额外空间，即空间复杂度要求O(1)，说明没办法用辅助数组。
然后这个题其实是上一题 删除有序数组中的重复项 的升级版，稍微麻烦了一点而已，思路完全是一样的。
同样是要判断连续的重复字符，只不过现在还要追加其数目而已。

class Solution:
    def compress(self, chars: List[str]) -> int:
        N = len(chars)
        if N <= 1:
            return N

        s, f = 0, 1
        old = 0 # 需要设置一个变量来记录重复区域的起始index
        while f <= N:
            if f==N or chars[f] != chars[s]:
                # 此时f已经走出了重复区域来到了新的区域(f==N时代表list已经遍历完)
                w = f-old # 则上一段重复区域的长度就是 f 减去上一段重复区域的起始index: old
                if w>=2:  # 如果该区域长度至少为2, 则说明要添加数字
                    for ch in list(str(w)):
                        s+=1
                        chars[s] = str(ch)
                if f < N:
                    # 把新区域的字符添加上
                    s+=1      
                    chars[s] = chars[f]
                    old = f # 现在已经处理完上一段重复区域, 则old更新为新重复区域的起始index
            f += 1
        return s+1

2.3.2.3 删除有序数组中的重复项II

LeetCode 80.删除有序数组中的重复项II | | 返回目录2.3.2

思路：思路和前面两道题一脉相承，代码稍加改动即可

class Solution:

    def removeDuplicates(self, nums: List[int]) -> int:
        N = len(nums)
        s, f = 0, 1
        begin = 0

        while f <= N:
            # 这里的code写法和前面两道题不同，算是拓展一下思路
            # 这里是f和它前一位比较, 来判断重复区域是否结束
            if f == N or nums[f] != nums[f-1]:
                # f-1 就是重复区域的末尾index
                nums[s] = nums[f-1]
                s += 1
                cnt = f - begin
                begin = f
                if cnt >= 2:
                    nums[s] = nums[f-1]
                    s += 1

            f += 1
        return s

2.3.2.4 移除元素

LeetCode 27.移除元素 | | 返回目录2.3.2

思路：和上面的题目一脉相承。用虚拟栈的思路会很容易理解。

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        N=len(nums)
        # 慢指针充当虚拟栈栈顶索引, 快指针用来遍历数组
        s, f = -1, 0
        while f < N:
            if nums[f] != val:
                # 将虚拟栈扩充一位, 并且将数放入栈顶
                s += 1
                nums[s] = nums[f]
            f += 1
        # 虚拟栈数据范围 0~s 共s+1个数字
        return s+1

2.3.2.5 移动零

LeetCode 283.移动零 | | 返回目录2.3.2

思路: partition 问题，注意，下面的代码是非稳定的
因为不同的0的相对次序其实会变化，只不过题目只要求非0数据相对次序不变，所以还是能保证的。
后面的章节讲排序问题的快速排序讨论, 会详细讲 partition 问题;
这里还是先用虚拟栈的思考方式来理解更方便一点。

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        N = len(nums)
        # 慢指针充当虚拟栈栈顶索引，快指针用来遍历数组
        ps, pf = -1, 0
        while pf <N:
            if nums[pf] != 0:
                # 虚拟栈扩充一格
                ps += 1
                # 栈顶位置的原始数字, 和 pf 位置的数字进行交换, 
                # 就把pf位置的数放到栈里来了, 同时将原始数字放到栈外面去了
                nums[pf], nums[ps] = nums[ps], nums[pf]
            pf += 1

2.3.2.6 递增的三元子序列

LeetCode 334.递增的三元子序列 | | 返回目录2.3.2

思路：这个题虽然没有显式的使用快慢指针，但是思想是借鉴了快慢指针的。
假设我们要找3个数a,b,c满足 a < b < c 的条件，那么a应该尽可能的小，b也应该在大于a的情况下尽可能的小，这样才容易去找到满足条件的c。
那么，比方说我们如何找到一个数组中，最小的数呢（不调用min）？？那就是设定一个极大的初始值，遍历一道数组，在遍历过程中发现更小的数，就更新，最终就能找到这个最小的数。
借鉴这个思想，我们的代码如下

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        a = b = float('inf')
        for num in nums:
            if num <= a:
                # 这样能够保证在遍历过的数字中，a一定是最小的那个数
                a = num 
            elif num <=b:
                # elif隐含的条件是不满足上面的条件，即不满足小于等于a
                # 所以b一定能取到在遍历过的数目当中，位于a后面的，比a大的数当中，最小的一个数
                b = num 
            else:
                # 在继续变量的过程中，只要遇到一个数不满足上面的条件，即比a和b都大
                # 这个数就能够充当 c 的角色
                # c = num 
                return True
        return False

2.3.2.7 最长湍流子数组

LeetCode 978.最长湍流子数组 | | 返回目录2.3.2

思路：该题在对撞指针中讲过一次，但是更好的解法是使用快慢指针。
具体的思路可以看code中的注释，采用快慢指针要快许多

class Solution:
    def maxTurbulenceSize(self, arr: List[int]) -> int:
        '''
        注意到题目中给的例子，1个元素也算湍流，2个不相等的数也能组成宽度为2的湍流
        其实不用像 山脉宽度 那样每次从一个中心点，向着左右扩散
        湍流可以选择一个起始点，从左往右的方向一直扩散，比如：
        情况1：arr[0] > arr[1] < arr[2] > ··· 
        或 情况2：arr[0] < arr[1] > arr[2] < ···
        考虑用快慢指针，一个维护湍流的起点，另一个维护湍流的终点
        '''
        N, width = len(arr), 1
        L, R = 0 ,1
        while R < N: # 当湍流的右边界没有超过数组
            # 情况 1
            if arr[L] > arr[R]:
                flag = -1
                # 如果右边一直能满足湍流的条件，就一直往右扩散
                # 这里是通过乘以 (-1)^k 来变相控制 大于/小于符号, 注意这里用的是 >
                while R < N-1 and (arr[R]- arr[R+1]) * flag > 0:
                    R += 1
                    flag *= -1
                # 循环结束后, R 指向该组湍流的最后一个满足条件的元素
                width = max(width, R-L+1)                
            # 情况 2
            elif arr[L] < arr[R]:
                flag = -1 
                # 这里是通过乘以 (-1)^k 来变相控制 大于/小于符号, 注意这里用的是 < 
                while R < N-1 and (arr[R]- arr[R+1]) * flag < 0:
                    R += 1
                    flag *= -1
                width = max(width, R-L+1)
            # 连续两个数字相等，直接pass
            else:
                pass
            # 更新起点和终点
            L = R 
            R +=1
        return width

2.3.2.8 最大连续 1 的个数

LeetCode 485.最大连续 1 的个数 | | 返回目录2.3.2

思路：该题在 2-2 数组相关题目的 2.2.1.3 已经见过，现在再用快慢指针的思路，更容易理解。

class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        L, R =-1, 0
        # 慢指针用来标记连续1区域的左边界, 快指针用来判断当前位置是否是1
        gap = 0
        for R in range(0, len(nums)):
            if nums[R] == 1:
                gap = max(gap, R-L)
            else:
                L = R 
        return gap