Nemo
Nemo
LeetCode-数组类算法题精析
LeetCode-数组类算法题精析

数组类算法精析

介绍

面试中的算法问题,有很多并不需要复杂的数据结构支撑。就是用数组,就能考察出很多东西了。其实,经典的排序问题,二分搜索等等问题,就是在数组这种最基础的结构中处理问题的,今天主要介绍 LeetCode 中典型的数组类问题,主要介绍这类问题的一些常用解法:做好初始定、基础算法思想应用、对撞指针、滑动窗口法等。

本期全部解答由创作嘉宾特邀提供,将以 Python 语言呈现。

做好初始定义

做数组类算法问题的时候,我们常常需要定义一个变量,明确该变量的定义,并且在书写整个逻辑的时候,要不停的维护住这个变量的意义。也特别需要注意初始值和边界的问题。

移动零

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

示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

说明:

  1. 必须在原数组上操作,不能拷贝额外的数组。
  2. 尽量减少操作次数。
解答

法1:遍历整个数组,遇到0就删除0,在数组后面尾加0

class Solution(object):
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        for i in nums:
            if i == 0:
                nums.append(0)
                nums.remove(0)
        return nums

python中的数组.remove方法是删除数组中第一个符合要求的元素

python 数组的del ,remove,pop区别

法2

第一次遇到非零元素,将非零元素与数组nums[0]互换,第二次遇到非零元素,将非零元素与nums[1]互换,第三次遇到非零元素,将非零元素与nums[2],以此类推,直到遍历完数组。

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

移动零 – 解题思路:

首先遍历一遍数列,用另个数列按顺序存储所有非 0 的元素,在将存储的非零元素按顺序复制到原数列中,空位补 0 即可。

https://kanghaov-img-1256185664.file.myqcloud.com/2019/08/02/5d44302d9a3cd.png

直观的解题思路新建额外的数组,不符合要求,但是对于我们下面的优化算法很有启示

简单的优化。

只要把数组中所有的非零元素,按顺序给数组的前段元素位赋值,剩下的全部直接赋值 0。我们定义一个 nums 0…i 表示为非 0 元素的数组,之后在遍历数列的时候不断维护这个定义。

class Solution:
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        i = -1
        j = 0
        # nums[0....i]表示非0元素的数列,初始值i=-1
        while j <= n-1:
            if nums[j] != 0:
                i += 1
                nums[i] = nums[j]
            j += 1
        for k in range(i+1, n):
            nums[k] = 0

移除元素

给定一个数组 nums 和一个值 val,你需要原地移除所有数值等于 val 的元素,返回移除后数组的新长度。

不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1:

给定 nums = [3,2,2,3], val = 3,

函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。

你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,1,2,2,3,0,4,2], val = 2,

函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

注意这五个元素可为任意顺序。

你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数,但输出的答案是数组呢?

请注意,输入数组是以“引用”方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

“`c++
// nums 是以“引用”方式传递的。也就是说,不对实参作任何拷贝
int len = removeElement(nums, val);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}

<pre><code class=""><br /><br /><br />##### 解答

循环判断val是否在数组中,在就删除。

“`python
class Solution(object):
def removeElement(self, nums, val):
“””
:type nums: List[int]
:type val: int
:rtype: int
“””
while True:
if val in nums:
nums.remove(val)
else:
break

return len(nums)

官方解答

定义 nums[0…i] 为非 val 的数列,遍历整个数列不断的维护这个定义

class Solution:
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        n = len(nums)
        i = -1
        # 定义nums[0...i]为非val的数列
        j = 0
        while j <= n-1:
            if nums[j] != val:
                i += 1
                nums[i] = nums[j]
            j += 1
        return i+1

删除排序数组中的重复项

给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。

不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1:

给定数组 nums = [1,1,2],

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。

你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,0,1,1,1,2,2,3,3,4],

函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数,但输出的答案是数组呢?

请注意,输入数组是以“引用”方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说,不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}
解答

需要做两件事:

  • 统计数组中不同数字数量k;

  • 修改数组前k个元素为这些不同数字。

由于数组已经完成排序,因此设定第一个指针i,遍历数组,每遇到nums[i] != nums[i – 1],就说明遇到了新的不同数字,记录之;

设定第二个指针k,每遇到新的不同数字执行k += 1,k有两个用途:

  • 记录数组中不同数字的数量;

  • 作为修改数组元素的index。

最终,返回k即可。

class Solution:
    def removeDuplicates(self, nums: [int]) -> int:
        if not nums: return 0
        k = 1
        for i in range(1, len(nums)):
            if nums[i] != nums[i - 1]:
                nums[k] = nums[i]
                k += 1
        return k


官方解答

定义 nums[0…i] 为为非重复数列,遍历整个数列不断的维护这个定义。

class Solution:
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        if n == 0 or n ==1:
            return n
        # nums[0,i]为非重复数列
        i = 0
        j = i + 1
        while j <= n-1:
            if nums[j] != nums[i]:
                # 指向同一个元素不需要赋值
                if i + 1 != j:
                    nums[i+1] = nums[j]
                i += 1
            j += 1
        return i + 1

删除排序数组中的重复项 II

给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素最多出现两次,返回移除后数组的新长度。

不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1:

给定 nums = [1,1,1,2,2,3],

函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。

你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,0,1,1,1,1,2,3,3],

函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。

你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数,但输出的答案是数组呢?

请注意,输入数组是以“引用”方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说,不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

解答

倒序比较,三个相等就剔除

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        for i in range(len(nums)-3,-1,-1):
            if nums[i] == nums[i+1] == nums[i+2]:
                nums.pop(i)

官方解答

定义 nums[0…i] 满足每个元素最多出现两次,初始值 i=-1,遍历整个数列不断的维护这个定义。

class Solution:
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        if (n <= 2):
            return n
        # nums[0...i]是符合要求的,
        i = 1
        k = i - 1
        j = i + 1

        while j <= n-1:
            if (nums[j] != nums[i]) or (nums[j] == nums[i] and nums[j] != nums[k]):
                k = i
                nums[i+1] = nums[j]
                i += 1
            j += 1

        return i + 1

运用基础算法思想

典型的排序算法思想、二分查找思想在解 LeetCode 题目时很有用。

颜色分类

给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。

此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

注意:
不能使用代码库中的排序函数来解决这道题。

示例:

输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]

进阶:

  • 一个直观的解决方案是使用计数排序的两趟扫描算法。
    首先,迭代计算出0、1 和 2 元素的个数,然后按照0、1、2的排序,重写当前数组。
  • 你能想出一个仅使用常数空间的一趟扫描算法吗?
解答

基数排序法

可以采用基数排序法的思想,用一个数组记录下 0,1,3 的次数,后重排,这个算法对数组进行了两次遍历,其实有一种只进行一次遍历的方法。

三路快速排序方法

设置三个 lt, gt, i 定义:nums[0…lt] == 0,nums[lt+1…i-1] = 1,nums[gt…n-1] == 2,遍历一遍改数列保持这个定义。

https://kanghaov-img-1256185664.file.myqcloud.com/2019/08/04/f7af841729e2c.png

class Solution:
    def sortColors(self, nums):
        n = len(nums)

        lt = -1
        gt = n
        i = 0

        while i < gt:
            if nums[i] == 0:
                lt += 1
                nums[lt], nums[i] = nums[i], nums[lt]
                i += 1
            elif nums[i] == 2:
                gt -= 1
                nums[gt], nums[i] = nums[i], nums[gt]
            else:
                i += 1

数组中的第K个最大元素

在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

说明:

你可以假设 k 总是有效的,且 1 ≤ k ≤ 数组的长度。

解答

思路:先排序,再索引,排序时间复杂度为O(nlogn)

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        nums.sort()
        return nums[len(nums)-k]

官方解答

利用快速排序的思想,从数组 S 中随机找出一个元素 X,把数组分为两部分 Sa 和 Sb。Sa 中的元素大于等于 X,Sb 中元素小于 X。这时有两种情况:

  • Sa 中元素的个数小于 k,则 Sb 中的第 k-|Sa| 个元素即为第k大数;
  • Sa 中元素的个数大于等于 k,则返回 Sa 中的第 k 大数。时间复杂度近似为 O(n)
class Solution:
    # 采用快速排序方法,分成的数列左边大于右边
    def findKthLargest(self, nums, k):
        n = len(nums)
        if (k > n):
            return
        index = self.quickSort(nums, 0, n-1, k)
        return nums[index]


    def quickSort(self, nums, l, r, k):
        if l >= r:
            return l
        p = self.partition(nums, l, r)
        if p + 1 == k:
            return p
        if p + 1 > k:
            return self.quickSort(nums, l, p -1, k)
        else:
            return self.quickSort(nums, p + 1, r, k)


    def partition(self, nums, l, r):
        v = nums[l]
        j = l
        i = l + 1
        while i <= r:
            if nums[i] >= v:
                nums[j+1],nums[i] = nums[i],nums[j+1]
                j += 1
            i += 1
        nums[l], nums[j] = nums[j], nums[l]
        return j

合并两个有序数组

给定两个有序整数数组 nums1nums2,将 nums2 合并到 nums1使得 num1 成为一个有序数组。

说明:

  • 初始化 nums1nums2 的元素数量分别为 mn
  • 你可以假设 nums1 有足够的空间(空间大小大于或等于 m + n)来保存 nums2 中的元素。

示例:

输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

输出: [1,2,2,3,5,6]
解答

最朴素的解法就是将两个数组合并之后再排序。该算法只需要一行(Java是2行),时间复杂度较差,为O((n+m)log(n+m))。这是由于这种方法没有利用两个数组本身已经有序这一点。

class Solution(object):
    def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: void Do not return anything, modify nums1 in-place instead.
        """
        nums1[:] = sorted(nums1[:m] + nums2)
官方解答

常规解题思路

其实这道题就是归并排序 partition 的过程(将两个有序的数列合并成一个有序数列),直观的思路是新建一个新的数列,遍历 nums1 和 nums2 这两个数列,将新建的数列有序后又赋值给 nums1 后返回。其实还有一种方法不需要开辟新的空间。

尾插法

由于 nums1 有足够的空间(空间大小大于或等于 m + n)来保存 nums2 中的元素,所以从 k=m+n-1 开始,分别遍历 nums1[m…0] 和 nums2[n…0] 中选取值大的。

class Solution:
    def merge(self, nums1, m, nums2, n):

        # 尾插入法
        if (n < 1):
            return
        if (m < 1):
            nums1[0:n] = nums2[0:n]
            return
        k = m + n - 1
        i = m - 1
        j = n - 1

        while k >= 0:
            if (nums1[i] > nums2[j] and i >= 0) or (j < 0 and i >= 0):
                nums1[k] = nums1[i]
                k -= 1
                i -= 1

            if (nums2[j] >= nums1[i] and j >= 0) or (i < 0 and j >=0):
                nums1[k] = nums2[j]
                k -= 1
                j -= 1

双索引技巧 – 对撞指针

有一些 LeetCode 题目,我们可以采用对撞指针进行求解:指针 i 和 j 分别指向数组的第一个元素和最后一个元素,然后指针 i 不断向前, 指针 j 不断递减,直到 i = j(当然具体的逻辑操作根据题目的变化而变化)。

两数之和 II – 输入有序数组

给定一个已按照升序排列 的有序数组,找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 index1 和 index2,其中 index1 必须小于 index2

说明:

  • 返回的下标值(index1 和 index2)不是从零开始的。
  • 你可以假设每个输入只对应唯一的答案,而且你不可以重复使用相同的元素。

示例:

输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

解答

双指针,但是返回的是列表套列表

def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        # 定义一列表专门用来保存结果集
        index_list = []
        for start in range(len(numbers)):
            for end in range(start+1, len(numbers)):
                if numbers[start]+numbers[end] == target:
                    index_list.extend([start+1, end+1])
                    break
        return index_list


换一种双指针逼近法:

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        n = len(numbers)
        left = 0
        right = n-1
        while left < right:
            if numbers[left] + numbers[right] > target:
                right -= 1
            elif numbers[left] + numbers[right] < target:
                left += 1
            else:
                return [left+1,right+1]

复杂度分析:

  • 时间复杂度:O(N)O(N),这里 NN 表示数组中的元素的大小。
  • 空间复杂度:O(1)O(1),只使用了常数个变量。

二分查找

思路分析

二分查找,起点得固定,因此,外面要套上一层循环。

参考代码

from typing import List


class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        size = len(numbers)
        for left in range(size - 1):
            right = self.__binary_search(numbers, left + 1, size - 1, target - numbers[left])
            if right != -1:
                return [left + 1, right + 1]

    def __binary_search(self, numbers, left, right, target):
        # 在子区间 [left, right] 找 target
        while left < right:
            mid = (left + right) >> 1
            if numbers[mid] < target:
                left = mid + 1
            else:
                right = mid
        return left if numbers[left] == target else -1


复杂度分析:

  • 时间复杂度:O(N \log N)O(NlogN),这里 NN 表示数组中的元素的大小,外层循环是线性时间复杂度,内层循环是对数级别的时间复杂度。
  • 空间复杂度:O(1)O(1),只使用了常数个变量。
官方解法

暴力解法

双层遍历,时间复杂度为 O(n^2),暴力解法没有充分利用原数组的性质 —— 有序,本文不采用。

当我们看到数列有序的时候,就应该想到可以用二分搜索法。

二分搜索法

遍历每个 nums[i],在剩余数组中查找 target-nums[i] 的值,时间复杂度为 O(n log n)。

https://kanghaov-img-1256185664.file.myqcloud.com/2019/08/04/1a29473a04fcf.png

对撞指针法

们首先判断首尾两项的和是不是 target,如果比 target 小,那么我们左边 (i)+1 位置的数(比左边位置的数大)再和右相相加,继续判断。如果比 target 大,那么我们右边 (j)-1 位置的数(比右边位置的数小)再和左相相加,继续判断。我们通过这样不断放缩的过程,就可以在 O(n) 的时间复杂度内找到对应的坐标位置。
https://kanghaov-img-1256185664.file.myqcloud.com/2019/08/04/24ce2ef80e7e1.png

class Solution:
    def twoSum(self, numbers, target):
        n = len(numbers)
        if (n < 2):
            return []
        i = 0
        j = n-1
        while i < j:
            if numbers[i] + numbers[j] == target:
                return [i+1,j+1]
            elif numbers[i] + numbers[j] < target:
                i += 1
            else:
                j -= 1
        return []

验证回文串

给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。

说明:本题中,我们将空字符串定义为有效的回文串。

示例 1:

输入: "A man, a plan, a canal: Panama"
输出: true

示例 2:

输入: "race a car"
输出: false

解答

掌握一些str的新方法,思路清晰:

class Solution:
    def isPalindrome(self, s: str) -> bool:
        s1 = filter(str.isalnum, s)
        s2 = "".join(s1)
        s3 = s2.lower()
        s_reverse = s3[::-1]
        if s_reverse == s3:
            return True
        else:
            return False
官方解答

采用对撞指针。

class Solution:
    def isPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """

        n = len(s)
        i = 0
        j = n-1

        while i < j:
            if s[i].isalnum() == False:
                i += 1
                continue
            if s[j].isalnum() == False:
                j -= 1
                continue
            if s[i].lower() != s[j].lower():
                return False
            i += 1
            j -= 1
        return True

注:isalnum( ) 判断一个字符是否为数字或者字母,lower( ) 字符转小写函数。

反转字符串中的元音字母

编写一个函数,以字符串作为输入,反转该字符串中的元音字母。

示例 1:

输入: "hello"
输出: "holle"

示例 2:

输入: "leetcode"
输出: "leotcede"

说明:
元音字母不包含字母”y”。

解答
class Solution:
    def reverseVowels(self, s: str) -> str:
        vowels = ['a', 'e', 'i', 'o', 'u', "A", "E", "I", "O", "U"]
        s = list(s)
        low = 0
        high= len(s) -1
        while low < high:
            if s[low] not in vowels:
                low += 1
                continue #这个不能漏
            elif s[high] not in vowels:
                high -= 1
                continue
            else:
                s[low],s[high] = s[high],s[low]
            low += 1
            high -= 1
            return ''.join(s)

结果


274 / 481 个通过测试用例 状态:解答错误 提交时间:25 分钟之前 输入: "leetcode" 输出: "leetcode" 预期: "leotcede"
官方解答

同样,也是采用对撞指针。

class Solution:
    def reverseVowels(self, s):
        """
        :type s: str
        :rtype: str
        """

        ss = list(s)

        aeiou = ['a', 'e', 'i', 'o', 'u', 'A','E','I','O','U']
        n = len(s)
        i = 0
        j = n-1

        while i < j:
            if ss[i] not in aeiou:
                i += 1
                continue
            if ss[j] not in aeiou:
                j -= 1
                continue
            if (i < j):
                ss[i], ss[j] = ss[j], ss[i]
            i += 1
            j -= 1
        d = ''
        return d.join(ss)

盛最多水的容器

给定 n 个非负整数 a1,a2,…,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明:你不能倾斜容器,且 n 的值至少为 2。

https://kanghaov-img-1256185664.file.myqcloud.com/2019/08/13/4c856afaac123.jpg

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。

示例:

输入: [1,8,6,2,5,4,8,3,7]
输出: 49

解答
思路:

算法流程: 设置双指针 i,j 分别位于容器壁两端,根据规则移动指针(后续说明),并且更新面积最大值 res,直到 i == j 时返回 res

指针移动规则与证明: 每次选定围成水槽两板高度 h[i],h[j] 中的短板,向中间收窄 11 格。以下证明:

  • 设每一状态下水槽面积为 S(i,j),(0 <= i < j < n),由于水槽的实际高度由两板中的短板决定,则可得面积公式 S(i, j) = min(h[i], h[j]) × (j – i)。

  • 在每一个状态下,无论长板或短板收窄 11 格,都会导致水槽 底边宽度 -1−1:

    • 若向内移动短板,水槽的短板 min(h[i],h[j]) 可能变大,因此水槽面积 *S(i,j) 可能增大。

    • 若向内移动长板,水槽的短板 min(h[i],h[j*]) 不变或变小,下个水槽的面积一定小于当前水槽面积。

  • 因此,向内收窄短板可以获取面积最大值。换个角度理解:

    • 若不指定移动规则,所有移动出现的 S(i,j) 的状态数为 *C(n,2),即暴力枚举出所有状态。
  • 在状态 S(i, j)S(i,j) 下向内移动短板至 S(i+1,j)(假设h[i]<h[j] ),则相当于消去了 {S(i, j – 1), S(i, j – 2), … , S(i, i + 1)}S(i,j−1),S(i,j−2),…,S(i,i+1) 状态集合。而所有消去状态的面积一定 <= S(i, j):

      • 短板高度:相比S(i,j) 相同或更短(<=h[i*]);
    • 底边宽度:相比S(i,j*) 更短。
    • 因此所有消去的状态的面积都 < S(i, j)<S(i,j)。通俗的讲,我们每次向内移动短板,所有的消去状态都不会导致丢失面积最大值 。
  • 复杂度分析:
    • 时间复杂度 O(N)O(N),双指针遍历一次底边宽度 NN 。
    • 空间复杂度 O(1)O(1),指针使用常数额外空间。

https://kanghaov-img-1256185664.file.myqcloud.com/2019/08/13/ba3f49c7c8776.png

https://kanghaov-img-1256185664.file.myqcloud.com/2019/08/13/ded7c908a97f2.png

https://kanghaov-img-1256185664.file.myqcloud.com/2019/08/13/7301485ab03a9.png

https://kanghaov-img-1256185664.file.myqcloud.com/2019/08/13/5e0fb235a7706.png

https://kanghaov-img-1256185664.file.myqcloud.com/2019/08/13/49400278faaf9.png

https://kanghaov-img-1256185664.file.myqcloud.com/2019/08/13/ac62b0180376a.png

https://kanghaov-img-1256185664.file.myqcloud.com/2019/08/13/792805a5a9756.png

https://kanghaov-img-1256185664.file.myqcloud.com/2019/08/13/0599db0548cc1.png

class Solution:
    def maxArea(self, height: List[int]) -> int:
        i, j, res = 0, len(height) - 1, 0
        while i < j:
            if height[i] < height[j]:
                res = max(res, height[i] * (j - i))
                i += 1
            else:
                res = max(res, height[j] * (j - i))
                j -= 1
        return res

注意这里return的位置,要是return在while下则返回8,为错误值,平时要注意。

官方解答

我们在由线段长度构成的数组中使用两个指针,一个放在开始,一个置于末尾。 此外,我们会使用变量 maxarea 来持续存储到目前为止所获得的最大面积。 在每一步中,我们会找出指针所指向的两条线段形成的区域,更新 maxarea,并将指向较短线段的指针向较长线段那端移动一步。

class Solution:
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        n = len(height)
        i = 0
        j = n - 1

        maxarea = (j - i) * min(height[i], height[j])

        while i < j:
            if height[i] < height[j]:
                i += 1
            else:
                j -= 1
            maxarea = max(maxarea, (j - i) * min(height[i], height[j]))

        return maxarea

双索引技巧 – 滑动窗口

一些题目用滑动窗口方法解题,可以将时间复杂度控制在 O(n) 级别,最重要的是定义好滑动窗口,明确它要表达的意思,当然边界和初始值非常重要。

长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的连续子数组如果不存在符合条件的连续子数组,返回 0。

示例:

输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。

进阶:

如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。

解答

解题思路:
先考虑极限情况,数组的全部值求和刚好 ==s 那么我们要找到的最小长度 就是 数组长度,我们用双指针模拟一下找这个 极限情况的做法

步骤如下:
模拟了滑动窗口, 用快慢双指针原理来找到最小长度

  1. 双指针初始都在数组最左侧,0
  2. 保持左指针不动,移动右指针,并且对左右指针区间的值求和
  3. 判断 区间 和 是否>=s ,小于就继续移动右指针,直到找到一个区间和>=s后(极限情况就是右指针到了数组末尾后 区间和 == s ),开始进行区间内的判断,因为右指针指向的值可能会很大,所以需要对左指针的区间进行瘦身保证最小长度
  4. 右指针停住后,开始移动左侧,并且从区间和里移除掉左指针指向的值,一直移动到和<s后 左指针停住,继续移动右指针.
  5. 用min 来 判断每一次区间的数量大小
  6. 右指针到头的时候 结束并返回长度
class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        if sum(nums) == s:
            return len(nums)
        if sum(nums) < s:
            return 0
        left = 0
        sum_temp = 0
        min_temp = len(nums)
        for right in range(len(nums)):
            sum_temp += nums[right]
            while sum_temp >= s: # 这个条件不要忘了
                min_temp = min(min_temp,right-left+1)
                sum_temp -= nums[left]
                left += 1

        return min_temp
官方解答

要求是连续子数组,所以我们必须定义 i,j两个指针,i 向前遍历,j 向后遍历,相当与一个滑块,这样所有的子数组都会在 [i…j] 中出现,如果 nums[i..j] 的和小于目标值 s,那么j向后移一位,再次比较,直到大于目标值 s 之后,i 向前移动一位,缩小数组的长度。遍历到i到数组的最末端,就算结束了,如果不存在符合条件的就返回 0。

https://kanghaov-img-1256185664.file.myqcloud.com/2019/08/13/aa11cebb7d071.png

class Solution:
    def minSubArrayLen(self, s, nums):
        """
        :type s: int
        :type nums: List[int]
        :rtype: int
        """

        n = len(nums)
        if (n < 1 or sum(nums) < s):
            return 0

        # 维护一个滑动窗口nums[i,j], nums[i...j] < s
        i = 0
        j = -1
        total = 0
        res = n + 1
        while i <= n-1:
            if (j + 1 < n) and total < s:
                j += 1
                total += nums[j]
            else:
                total -= nums[i]
                i += 1

            if (total >= s):
                res = min(res, j-i+1)
        if res == n+1:
            return 0
        return res

总结

我们知道在准备面试的时候,刷算法题是一种捷径,特别是刷 LeetCode,但是不能一味的刷题,我们需要总结和思考,对于一些相似的题目我们应该多想想他们的思想,其实很多题的解题思路都是相近的。

Nemo版权所有丨如未注明,均为原创丨本网站采用BY-NC-SA协议进行授权,转载请注明转自:https://kanghaov.com/291.html
https://secure.gravatar.com/avatar/9fd8359b8faa6f7789f9623ba6041e4a?s=256&d=identicon&r=g

kanghaov

文章作者

推荐文章

发表评论

textsms
account_circle
email

Nemo

LeetCode-数组类算法题精析
数组类算法精析 介绍 面试中的算法问题,有很多并不需要复杂的数据结构支撑。就是用数组,就能考察出很多东西了。其实,经典的排序问题,二分搜索等等问题,就是在数组这种最基础的结构…
扫描二维码继续阅读
2019-08-13