問題描述：【Two Pointers】26. Remove Duplicates from Sorted Array

解題思路：

這道題是給一個(gè)排序好的數(shù)組匾南，通過修改原數(shù)組，使得前 K 個(gè)元素都不同豹爹，返回 K，要求使用 O(1) 的空間孩等。

第一種解法就是從左到右遍歷一遍，比較相鄰的元素权她，把重復(fù)的元素從數(shù)組中刪除，最后返回?cái)?shù)組的長度就是答案拾徙。雖然這樣做也能 AC暂衡，但是時(shí)間復(fù)雜度較高狂巢，代碼比較簡單雌续，略受啥。

第二種解法可以使用雙指針。使用一個(gè)慢指針 slow 指向開頭藤肢，然后使用一個(gè)快指針 fast 每次向后移動(dòng)莺奸。當(dāng) slow 和 fast 指向的元素不同温学，slow 加 1，然后將 fast 指向的元素賦值給 slow 指向的元素轧拄。這樣，數(shù)組遍歷完畢后料按，前 slow + 1 個(gè)元素都是不同的元素，返回 slow + 1 就是答案闷盔。

舉例：nums = [1,1,2,3]

• 剛開始 slow 指向 nums[0]，fast 指向 nums[1]
• nums[slow] == nums[fast]，fast 繼續(xù)向后移動(dòng)到 nums[2]；
• nums[slow] != nums[fast]，則將 slow 加 1 變成 1歉闰，執(zhí)行 nums[slow] = nums[fast] = 2卓起，此時(shí) nums = [1,2,2,3]和敬，fast 繼續(xù)向后移動(dòng)到 nums[3]；
• nums[slow] != nums[fast]戏阅，則將 slow 加 1 變成 2昼弟，執(zhí)行 nums[slow] = nums[fast] = 3，此時(shí) nums = [1,2,3,3]奕筐，結(jié)束芭逝；
• slow + 1 = 3 就是前 K 個(gè)不同的元素，返回 slow + 1即可桐汤。

時(shí)間復(fù)雜度為 O(N)抗果，空間復(fù)雜度為 O(1)墩划。

Python 3 實(shí)現(xiàn)：

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

解題思路：

這道題是給一個(gè)排序好的數(shù)組，通過修改原數(shù)組，使得每個(gè)元素最多只出現(xiàn)兩次晰房，把這些數(shù)（假設(shè)為 K 個(gè)）依次排到數(shù)組最前面海蔽，返回 K，要求使用 O(1) 的空間括改。

同上面的 Leetcode 80右冻，這道題也可以使用雙指針法求解：如果數(shù)組長度小于等于 2肃叶，則直接返回?cái)?shù)組長度就是答案。否則表制，使用慢指針 slow 始終指向要改變的位置鼎姊，使用快指針 fast 向后移動(dòng)悴侵。剛開始睬愤，兩指針都指向 nums[2] 的位置船老，每次，fast 都往后移動(dòng)一位拉盾。如果發(fā)現(xiàn) nums[slow-2] != nums[fast]凶异，就將 nums[fast] 賦值給 nums[slow]舷暮， 然后 slow + 1 繼續(xù)判斷。最后遍歷結(jié)束后噩茄，前 slow 個(gè)元素滿足題意下面，返回 slow 就是答案。

為什么 fast 要和 slow - 2 比較巢墅？以一個(gè)例子 nums = [0,0,0,1,2,2,3] 說明：

• 剛開始诸狭，slow 和 fast 都指向 nums[2] 處，即 slow = fast = 2君纫；
• fast 指向當(dāng)前元素 nums[2] 和 slow - 2 指向的元素 nums[0] 相同驯遇，說明相同的數(shù)字出現(xiàn)超過了兩次，因此 slow 處不改變蓄髓，fast 繼續(xù)向后移動(dòng)到 nums[3]叉庐；
• nums[slow-2] 和 nums[fast] 不相等，說明遇到一個(gè)不同的數(shù)字会喝，且不同數(shù)字出現(xiàn)次數(shù) <= 2陡叠，因此執(zhí)行 nums[slow] = nums[fast] 得到 nums = [0,0,1,1,2,2,3]，slow 加 1 指向下一個(gè)改變的位置 nums[3]肢执，fast 繼續(xù)移動(dòng)到 nums[4]枉阵；
• nums[slow-2] 和 nums[fast] 不相等，同理可得 nums = [0,0,1,2,2,2,3]预茄，slow 加 1 指向下一個(gè)改變的位置 nums[4]兴溜，fast 繼續(xù)移動(dòng)到 nums[5]；
• nums[slow-2] 和 nums[fast] 不相等耻陕，同理可得 nums = [0,0,1,2,2,2,3]拙徽，slow 加 1 指向下一個(gè)改變的位置 nums[5]，fast 繼續(xù)移動(dòng)到 nums[6]诗宣；
• nums[slow-2] 和 nums[fast] 不相等膘怕，同理可得 nums = [0,0,1,2,2,3,3]，slow 加 1 指向下一個(gè)改變的位置 nums[6]召庞，fast 繼續(xù)移動(dòng)岛心，結(jié)束；
• slow = 6篮灼，表示前六個(gè)元素是滿足題意的鹉梨，slow = 6 就是答案。

Python3 實(shí)現(xiàn)：

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

解題思路：

最大寬度坡晌坤。給一個(gè)數(shù)組 A逢艘，坡是元組 (i, j)旦袋，其中 i < j 且 A[i] <= A[j]。坡的寬度為 j - i它改。找出 A 中坡的最大寬度疤孕，如果不存在，返回 0 央拖。

首先看數(shù)據(jù)范圍祭阀，肯定不能使用 O(n^2) 的暴力解法，pass鲜戒。

方法1（Sort）：

這道題的實(shí)際上是求這樣一個(gè)問題：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] 的限制柏蘑，因此我們先要對(duì)數(shù)組，并且?guī)纤饕M(jìn)行升序排序粹庞。

注意：升序排序雖然滿足 A[i] <= A[j]咳焚，但是破壞了 i < j 這個(gè)限制條件，但是也不影響求解 max(j - i)庞溜。因?yàn)榧词蛊茐牧?i < j革半，使得某些 i >= j 計(jì)算出的 j - i <= 0，但是 max(j - i) 的最小值都是 0强缘，所以不用考慮 i < j 這個(gè)條件督惰，直接升序排序就好。

時(shí)間復(fù)雜度為 O(N*logN)旅掂，空間復(fù)雜度為 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. 構(gòu)造單調(diào)遞減棧：遍歷數(shù)組（第一個(gè)元素一定入棧）商虐，若棧頂元素大于當(dāng)前元素值觉阅，則將當(dāng)前元素對(duì)應(yīng)索引入棧。這樣做的道理是：假設(shè)棧頂有一個(gè)元素 a秘车，當(dāng)前元素為 b典勇，若 a <= b，則后續(xù)即使有一個(gè)元素 c 滿足 c > b （當(dāng)然 c > a）割笙，可能出現(xiàn)最大的坡度也應(yīng)該是 c 和 a 下標(biāo)之差伤溉，而不是 c 和 b 的板祝，因此棧頂元素小于等于當(dāng)前元素的值不應(yīng)該入棧（反證法）券时。
2. 求最大坡度：從后往前遍歷（for 循環(huán)），若棧不為空且棧頂元素小于等于當(dāng)前元素震檩，則更新最大值 i - stack[-1]抛虏，并彈出棧頂元素迂猴，重復(fù)上述操作（while 循環(huán)），否則向前移動(dòng)繼續(xù)判斷息尺。

舉例如下：A = [6,8,2,2,1,5,3]，ans = 0 更新結(jié)果

• 從左到右遍歷炭懊，得到遞減棧 stack = [0,2,4]（分別對(duì)應(yīng) 6、2（第一個(gè)）父阻、1）钠署；
• 從右到左遍歷 i = 6舰蟆，A[stack[-1]] = 1 <= A[6] = 3味悄，ans = max(ans, i - stack[-1]) = max(0, 6 - 4) = 2侍瑟；彈出 stack[-1] = 4，繼續(xù)判斷棧庭瑰；A[stack[-1]] = 2 <= A[6] = 3，ans = max(ans, i - stack[-1]) = max(2, 6 - 2) = 4穷吮； 彈出 stack[-1] = 2捡鱼，繼續(xù)判斷棧伟墙；A[stack[-1]] = 6 > A[6] = 3戳葵，不滿足棧頂元素小于等于當(dāng)前元素的條件生蚁，i 向前移動(dòng)伤锚；
• i = 5、4、3、2 均不滿足棧頂元素小于等于當(dāng)前元素的條件借嗽，i 繼續(xù)向前移動(dòng)；
• i = 1，A[stack[-1]] = 6 <= A[1] = 8，ans = max(ans, i - stack[-1]) = max(4, 1 - 0) = 4缸废；彈出 stack[-1] = 0亡电，繼續(xù)判斷棧腕唧；棧為空瘾英，i 向前移動(dòng)枣接；
• i = 0，棧為空缺谴，遍歷結(jié)束但惶，得到 ans = 4。

時(shí)間復(fù)雜度為 O(N)湿蛔，空間復(fù)雜度為 O(N)榆骚。

Python3 實(shí)現(xiàn)：

class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        N = len(A)
        stack = [0]  # 遞減棧，棧中存儲(chǔ)遞減數(shù)字的索引
        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]最遠(yuǎn)的值
                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])

因此，我們使用左右遍歷法捌省，從左到右求最小值苫纤、從右到左求最大值，分別保存在數(shù)組 leftMin 和 rightMax 中纲缓。然后卷拘，使用雙指針 i 和 j 分別指向 leftMin[i] 和 rightMax[j]（初始 i = 0, j = 1），根據(jù)兩者關(guān)系移動(dòng)指針祝高，并更新 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)怎披，退出，結(jié)果 ans = 3瓶摆。

實(shí)際上凉逛，在最后從左到右遍歷的過程中，我們可以使用一個(gè)變量 left_min 來更新最小值群井，因此不用存儲(chǔ)到數(shù)組中状飞。這種做法類似于 Leetcode 【Array】915. Partition Array into Disjoint Intervals。時(shí)間復(fù)雜度為 O(N)书斜，空間復(fù)雜度為 O(N)诬辈。

Python3 實(shí)現(xiàn)：

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