class Solution:
    def maxDistance(self, arrays: List[List[int]]) -> int:
        res = 0
        n = len(arrays[0])
        min_val = arrays[0][0]
        max_val = arrays[0][-1]
        
        for i in range(1, len(arrays)):
            n = len(arrays[i])
            res = max(res, max(abs(arrays[i][n - 1] - min_val), 
                            abs(max_val - arrays[i][0])))
            min_val = min(min_val, arrays[i][0])
            max_val = max(max_val, arrays[i][-1])
        
        return res

class Solution(object):
    def wiggleSort(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        nums.sort()
        temp = 0
        for i in range(1, len(nums)-1,2):
            # nums[i+1], nums[i] = nums[i], nums[i+1]
                temp = nums[i]
                nums[i] = nums[i+1]
                nums[i+1] = temp
        return nums 
# 时间复杂度O(n)
	def wiggleSort(self, nums):
        for i in range(len(nums)-1):
            if ((i%2 == 0 and nums[i] > nums[i+1]) or (i%2 == 1 and nums[i] < nums[i+1])):
                nums[i], nums[i+1] = nums[i+1], nums[i]

class Solution(object):
    def confusingNumber(self, n):
        """
        :type n: int
        :rtype: bool
        """
        dic = {'0':'0','1':'1','8':'8','6':'9','9':'6'}
        s = str(n)
        rev_s = ""
        for i in s:
            if i not in dic:
                return False
            rev_s = dic[i] + rev_s
        return rev_s!=s

class Solution(object):
    def stringShift(self, s, shift):
        """
        :type s: str
        :type shift: List[List[int]]
        :rtype: str
        """
        left_sum = 0
        right_sum = 0
        for direction, amount in shift:
            if direction == 0:
                left_sum += amount
            else:
                right_sum += amount
        total = (right_sum-left_sum)%len(s)
        if total < 0:
            total += len(s)
        # 切片操作
        return s[-total:] + s[:-total]

class Solution(object):
    def isOneEditDistance(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        len_s,len_t = len(s),len(t)
        # 保证s长度要小于t   
        if len_s > len_t:
            return isOneEditDistance(t,s)
        # 长度超过1的字符距离一定不满足题意
        if len_t - len_s > 1:
            return False
        # 找s和t的前len(s)项是否相同
        for i in range(len_s):
            # 出现一个字符不同
            if s[i] != t[i]:
                # 若长度相同则后面需要完全一样
                if len_s == len_t:
                    return s[i + 1:] == t[i + 1:]
                # 长度差为 1 时，s 从当前位置开始和 t 从下一个位置开始需相同
                else:
                    return s[i:] == t[i + 1:]
        # 前len(s)完全相同 
        return len_s + 1 == len_t

class Solution(object):
    def reverseWords(self, s):
        """
        :type s: List[str]
        :rtype: None Do not return anything, modify s in-place instead.
        """
        n = len(s)
        # 使用 Python 列表的 reverse() 方法将整个字符数组反转，这里reverse是创建了一个新的列表
        s.reverse()
        pre = 0
        for i in range(n):
            if s[i] ==' ':
                # 不可以用s[pre:i].reverse()，因为切片操作时这样会自动创建新的列表原始并没有修改
                s[pre:i] = reversed(s[pre:i])
                pre = i + 1
        # 处理最后一个单词，因为最后一个单词后面没有空格
        s[pre:] = reversed(s[pre:])
        return s 

# 模板 (伪代码)
class Solution:
    def problemName(self, s: str) -> int:
        # Step 1: 定义需要维护的变量们 (对于滑动窗口类题目，这些变量通常是最小长度，最大长度，或者哈希表)
        x, y = ..., ...

        # Step 2: 定义窗口的首尾端 (start, end)， 然后滑动窗口
        start = 0
        for end in range(len(s)):
            # Step 3: 更新需要维护的变量, 有的变量需要一个if语句来维护 (比如最大最小长度)
            x = new_x
            if condition:
                y = new_y

            '''
            ------------- 下面是两种情况，读者请根据题意二选1 -------------
            '''
            # Step 4 - 情况1
            # 如果题目的窗口长度固定：用一个if语句判断一下当前窗口长度是否超过限定长度 
            # 如果超过了，窗口左指针前移一个单位保证窗口长度固定, 在那之前, 先更新Step 1定义的(部分或所有)维护变量 
            if 窗口长度大于限定值:
                # 更新 (部分或所有) 维护变量 
                # 窗口左指针前移一个单位保证窗口长度固定

            # Step 4 - 情况2
            # 如果题目的窗口长度可变: 这个时候一般涉及到窗口是否合法的问题
            # 如果当前窗口不合法时, 用一个while去不断移动窗口左指针, 从而剔除非法元素直到窗口再次合法
            # 在左指针移动之前更新Step 1定义的(部分或所有)维护变量 
            while 不合法:
                # 更新 (部分或所有) 维护变量 
                # 不断移动窗口左指针直到窗口再次合法

        # Step 5: 返回答案
        return ...

def lengthOfLongestSubstringTwoDistinct(s):
    # 1. 定义需要维护的变量
    # 最大长度max_len，设计计算不重复元素格式需要哈希表hashmap
    max_len, hashmap = 0, {}
    # 2. 定义窗口首尾（start，end），滑动窗口
    start = 0
    for end in range(len(s)):
        # 3. 更新维护变量（max_len,hashmap）
        # 当前元素计数加一，一旦哈希表长度≤2，尝试更新最大长度
        hashmap[s[end]] = hashmap.get(s[end],0) + 1
        if len(hashmap) <=2:
            max_len = max(max_len,end-start+1)
        # 4. 因为窗口长度可变: 这个时候一般涉及到窗口是否合法的问题
        # 这时要用一个while去不断移动窗口左指针, 从而剔除非法元素直到窗口再次合法
        # 当哈希表长度>2时，移动左指针，直到哈希表长度≤2
        while len(hashmap) > 2:
            head = s[start]
            hashmap[head] -= 1
            if hashmap[head] == 0:
                del hashmap[head]
            start += 1
    return max_len

# 同样道理
# 无重复字符的最长子串
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # Step 1: 定义需要维护的变量, 本题求最大长度，所以需要定义max_len, 该题又涉及去重，因此还需要一个哈希表
        max_len, hashmap = 0, {}

        # Step 2: 定义窗口的首尾端 (start, end)， 然后滑动窗口
        start = 0
        for end in range(len(s)):
            # Step 3
            # 更新需要维护的变量 (max_len, hashmap)
            # i.e. 把窗口末端元素加入哈希表，使其频率加1，并且更新最大长度
            hashmap[s[end]] = hashmap.get(s[end], 0) + 1
            if len(hashmap) == end - start + 1:
                max_len = max(max_len, end - start + 1)
            
            # Step 4: 
            # 根据题意,  题目的窗口长度可变: 这个时候一般涉及到窗口是否合法的问题
            # 这时要用一个while去不断移动窗口左指针, 从而剔除非法元素直到窗口再次合法
            # 当窗口长度大于哈希表长度时候 (说明存在重复元素)，窗口不合法
            # 所以需要不断移动窗口左指针直到窗口再次合法, 同时提前更新需要维护的变量 (hashmap)
            while end - start + 1 > len(hashmap):
                head = s[start]
                hashmap[head] -= 1
                if hashmap[head] == 0:
                    del hashmap[head]
                start += 1
        # Step 5: 返回答案 (最大长度)
        return max_len
#长度最小的子数组
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        # Step 1: 定义需要维护的变量, 本题求最小长度，所以需要定义min_len, 本题又涉及求和，因此还需要一个sum变量
        min_len, sum_ = math.inf, 0

        # Step 2: 定义窗口的首尾端 (start, end)， 然后滑动窗口
        start = 0
        for end in range(len(nums)):
            # Step 3: 更新需要维护的变量 (min_len, sum_)
            sum_ += nums[end]
            if sum_ >= target:
                min_len = min(min_len, end - start + 1)

            # Step 4
            # 根据题意,  题目的窗口长度可变: 这个时候一般涉及到窗口是否合法的问题
            # 这时要用一个while去不断移动窗口左指针, 从而剔除非法元素直到窗口再次合法
            # 当sum_的值大于target时候，窗口不合法
            # 所以需要不断移动窗口左指针直到窗口再次合法, 同时提前更新需要维护的变量 (min_len， sum_)
            while sum_ >= target:
                min_len = min(min_len, end - start + 1)
                sum_ -= nums[start]
                start += 1
        # Step 5：返回答案 (最小长度)
        if min_len == math.inf:
            return 0
        return min_len

class Solution(object):
    def findMaxConsecutiveOnes(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        start = 0
        zero_count = 0
        max_length = 0
        # 1 1 1 1 0 1 1 0 
        for end in range(len(nums)):
            if nums[end] == 0:
                zero_count += 1
            while zero_count > 1:
                if nums[start] == 0:
                    zero_count -= 1
                start += 1
            max_length = max(max_length, end - start + 1)
        return max_length