Leetcode【26、80、962】 – 牛奶芝麻

Python publisher01 33℃ 0评论
问题描述:【Two Pointers】26. Remove Duplicates from Sorted Array
解题思路:

这道题是给一个排序好的数组,通过修改原数组,使得前 K 个元素都不同,返回 K,要求使用 O(1) 的空间。

第一种解法就是从左到右遍历一遍,比较相邻的元素,把重复的元素从数组中删除,最后返回数组的长度就是答案。虽然这样做也能 AC,但是时间复杂度较高,代码比较简单,略。

第二种解法可以使用双指针。使用一个慢指针 slow 指向开头,然后使用一个快指针 fast 每次向后移动。当 slow 和 fast 指向的元素不同,slow 加 1,然后将 fast 指向的元素赋值给 slow 指向的元素。这样,数组遍历完毕后,前 slow + 1 个元素都是不同的元素,返回 slow + 1 就是答案。

举例:nums = [1,1,2,3]

  • 刚开始 slow 指向 nums[0],fast 指向 nums[1]
  • nums[slow] == nums[fast],fast 继续向后移动到 nums[2];
  • nums[slow] != nums[fast],则将 slow 加 1 变成 1,执行 nums[slow] = nums[fast] = 2,此时 nums = [1,2,2,3],fast 继续向后移动到 nums[3];
  • nums[slow] != nums[fast],则将 slow 加 1 变成 2,执行 nums[slow] = nums[fast] = 3,此时 nums = [1,2,3,3],结束;
  • slow + 1 = 3 就是前 K 个不同的元素,返回 slow + 1即可。

时间复杂度为 O(N),空间复杂度为 O(1)。

Python 3 实现:
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums:
            return 0
        N = len(nums)
        slow, fast = 0, 1  # 快慢指针
        while slow < N and fast < N:
            if nums[slow] != nums[fast]:
                slow += 1
                nums[slow] = nums[fast]
            fast += 1
        return slow + 1  # 慢指针加1就是前面不同元素的长度

问题描述:【Two Pointers】80. Remove Duplicates from Sorted Array II
解题思路:

这道题是给一个排序好的数组,通过修改原数组,使得每个元素最多只出现两次,把这些数(假设为 K 个)依次排到数组最前面,返回 K,要求使用 O(1) 的空间。

同上面的 Leetcode 80,这道题也可以使用双指针法求解:如果数组长度小于等于 2,则直接返回数组长度就是答案。否则,使用慢指针 slow 始终指向要改变的位置,使用快指针 fast 向后移动。刚开始,两指针都指向 nums[2] 的位置,每次,fast 都往后移动一位。如果发现 nums[slow-2] != nums[fast],就将 nums[fast] 赋值给 nums[slow], 然后 slow + 1 继续判断。最后遍历结束后,前 slow 个元素满足题意,返回 slow 就是答案。

为什么 fast 要和 slow – 2 比较?以一个例子 nums = [0,0,0,1,2,2,3] 说明:

  • 刚开始,slow 和 fast 都指向 nums[2] 处,即 slow = fast = 2;
  • fast 指向当前元素 nums[2] 和 slow – 2 指向的元素 nums[0] 相同,说明相同的数字出现超过了两次,因此 slow 处不改变,fast 继续向后移动到 nums[3];
  • nums[slow-2] 和 nums[fast] 不相等,说明遇到一个不同的数字,且不同数字出现次数 <= 2,因此执行 nums[slow] = nums[fast] 得到 nums = [0,0,1,1,2,2,3],slow 加 1 指向下一个改变的位置 nums[3],fast 继续移动到 nums[4];
  • nums[slow-2] 和 nums[fast] 不相等,同理可得 nums = [0,0,1,2,2,2,3],slow 加 1 指向下一个改变的位置 nums[4],fast 继续移动到 nums[5];
  • nums[slow-2] 和 nums[fast] 不相等,同理可得 nums = [0,0,1,2,2,2,3],slow 加 1 指向下一个改变的位置 nums[5],fast 继续移动到 nums[6];
  • nums[slow-2] 和 nums[fast] 不相等,同理可得 nums = [0,0,1,2,2,3,3],slow 加 1 指向下一个改变的位置 nums[6],fast 继续移动,结束;
  • slow = 6,表示前六个元素是满足题意的,slow = 6 就是答案。
Python3 实现:
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        N = len(nums)
        if N <= 2:
            return N 
        slow = fast = 2
        while fast < N:
            if nums[slow-2] != nums[fast]:
                nums[slow] = nums[fast]
                slow += 1
            fast += 1
        return slow
print(Solution().removeDuplicates([0,0,0,1,2,2,3]))  # 6 -> [0,0,1,2,2,3]

问题描述:【Sort、Stack、Two Pointers】962. Maximum Width Ramp
解题思路:

最大宽度坡。给一个数组 A,坡是元组 (i, j),其中 i < j 且 A[i] <= A[j]。坡的宽度为 j – i。找出 A 中坡的最大宽度,如果不存在,返回 0 。

首先看数据范围,肯定不能使用 O(n^2) 的暴力解法,pass。

方法1(Sort):

这道题的实际上是求这样一个问题:max(j – i),i < j and A[i] <= A[j]。类似于 Leetcode 【Math、DP】121. Best Time to Buy and Sell Stock 方法 1 的解法:在遍历的过程中,i_min 指向最小值,并更新 j – i_min 的最大值。但是这道题还有 A[i] <= A[j] 的限制,因此我们先要对数组,并且带上索引进行升序排序。

注意:升序排序虽然满足 A[i] <= A[j],但是破坏了 i < j 这个限制条件,但是也不影响求解 max(j – i)。因为即使破坏了 i < j,使得某些 i >= j 计算出的 j – i <= 0,但是 max(j – i) 的最小值都是 0,所以不用考虑 i < j 这个条件,直接升序排序就好。

时间复杂度为 O(N*logN),空间复杂度为 O(N)。

class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        N = len(A)
        vk = sorted(zip(A, range(N)))  # 按照值升序,带上原来索引
        i_min, ans = vk[0][1], 0
        for _, j in vk:
            ans = max(ans, j - i_min)  # 更新最大值j-i
            i_min = min(i_min, j)  # 更新最小值i
        return ans

方法2(递减栈):

  1. 构造单调递减栈:遍历数组(第一个元素一定入栈),若栈顶元素大于当前元素值,则将当前元素对应索引入栈。这样做的道理是:假设栈顶有一个元素 a,当前元素为 b,若 a <= b,则后续即使有一个元素 c 满足 c > b (当然 c > a),可能出现最大的坡度也应该是 c 和 a 下标之差,而不是 c 和 b 的,因此栈顶元素小于等于当前元素的值不应该入栈(反证法)。
  2. 求最大坡度:从后往前遍历(for 循环),若栈不为空且栈顶元素小于等于当前元素,则更新最大值 i – stack[-1],并弹出栈顶元素,重复上述操作(while 循环),否则向前移动继续判断。

举例如下:A = [6,8,2,2,1,5,3],ans = 0 更新结果

  • 从左到右遍历,得到递减栈 stack = [0,2,4](分别对应 6、2(第一个)、1);
  • 从右到左遍历 i = 6,A[stack[-1]] = 1 <= A[6] = 3,ans = max(ans, i – stack[-1]) = max(0, 6 – 4) = 2;弹出 stack[-1] = 4,继续判断栈;A[stack[-1]] = 2 <= A[6] = 3,ans = max(ans, i – stack[-1]) = max(2, 6 – 2) = 4; 弹出 stack[-1] = 2,继续判断栈;A[stack[-1]] = 6 > A[6] = 3,不满足栈顶元素小于等于当前元素的条件,i 向前移动;
  • i = 5、4、3、2 均不满足栈顶元素小于等于当前元素的条件,i 继续向前移动;
  • i = 1,A[stack[-1]] = 6 <= A[1] = 8,ans = max(ans, i – stack[-1]) = max(4, 1 – 0) = 4;弹出 stack[-1] = 0,继续判断栈;栈为空,i 向前移动;
  • i = 0,栈为空,遍历结束,得到 ans = 4。

时间复杂度为 O(N),空间复杂度为 O(N)。

Python3 实现:

class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        N = len(A)
        stack = [0]  # 递减栈,栈中存储递减数字的索引
        for i in range(1, N):
            if A[stack[-1]] > A[i]:
                stack.append(i)
        ans = 0
        for i in range(N-1, -1, -1):  # 从后往前遍历
            while stack and A[stack[-1]] <= A[i]:  # 栈中找<=A[i]最远的值
                ans = max(ans, i - stack.pop())  # 更新最大j-i
        return ans

方法3(左右遍历法+双指针):

参考大牛的解题思路,做法很巧妙:

  • The idea is that for a tuple (i, j) such that j > i and A[i] <= A[j], if we can find an element A[k] on the right of A[j] (in other words k > j) such that A[k] >= A[i], we can then consider the tuple (i, k) since it increases our width.
  • Similarily for A[i], if we can find an element A[k] on the left of A[i] (k < i) such A[k] <= A[j], we can then consider the tuple (k, j) since it increases our width.
  • Based on this idea, we maintain 2 arrays: leftMin and rightMax
    leftMin[i]: smallest element on the left of ith index (from index 0 to i including A[i])
    rightMax[i]: largest element on the right of ith index (from i to n-1 including A[i])

因此,我们使用左右遍历法,从左到右求最小值、从右到左求最大值,分别保存在数组 leftMin 和 rightMax 中。然后,使用双指针 i 和 j 分别指向 leftMin[i] 和 rightMax[j](初始 i = 0, j = 1),根据两者关系移动指针,并更新 max(j – i)。举例如下:

A = [6,8,2,1,5,3]
leftMin = [6,6,2,1,1,1]
rightMax = [8,8,5,5,5,3]

  • leftMin[0] <= rightMax[1],ans = max(0, 1 – 0) = 1,j = 2;
  • leftMin[0] > rightMax[2],i = 1;
  • leftMin[1] > rightMax[2],i = 2;
  • leftMin[2] <= rightMax[2],ans = max(1, 2 – 2) = 1,j = 3;
  • leftMin[2] <= rightMax[3],ans = max(1, 3 – 2) = 1,j = 4;
  • leftMin[2] <= rightMax[4],ans = max(1, 4 – 2) = 2,j = 5;
  • leftMin[2] <= rightMax[5],ans = max(1, 5 – 2) = 3,j = 6;
  • 不满足 i < len(A) and j < len(A),退出,结果 ans = 3。

实际上,在最后从左到右遍历的过程中,我们可以使用一个变量 left_min 来更新最小值,因此不用存储到数组中。这种做法类似于 Leetcode 【Array】915. Partition Array into Disjoint Intervals时间复杂度为 O(N),空间复杂度为 O(N)。

Python3 实现:

class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        N = len(A)
        left_min = float("inf")
        right_max = [0] * N
        right_max[-1] = A[-1]
        for i in range(N-2, -1, -1):
            right_max[i] = max(right_max[i+1], A[i])
        i, j, ans = 0, 1, 0  # i和j分别指向左最小和右最大
        while i < N and j < N:
            left_min = min(left_min, A[i])
            if left_min <= right_max[j]:
                ans = max(ans, j-i)  # 更新最大值j-i
                j += 1
            else:
                i += 1
        return ans

© 著作权归作者所有,转载或内容合作请联系作者

你或许想:《去原作者写文章的地方

转载请注明:Python量化投资 » Leetcode【26、80、962】 – 牛奶芝麻

喜欢 (0)or分享 (0)
发表我的评论
取消评论
表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址