Leetcode【26、80、962】

问题描述：【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（递减栈）：

构造单调递减栈：遍历数组（第一个元素一定入栈），若栈顶元素大于当前元素值，则将当前元素对应索引入栈。这样做的道理是：假设栈顶有一个元素 a，当前元素为 b，若 a <= b，则后续即使有一个元素 c 满足 c > b （当然 c > a），可能出现最大的坡度也应该是 c 和 a 下标之差，而不是 c 和 b 的，因此栈顶元素小于等于当前元素的值不应该入栈（反证法）。
求最大坡度：从后往前遍历（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