这道题是给一个排序好的数组,通过修改原数组,使得前 K 个元素都不同,返回 K,要求使用 O(1) 的空间。
第一种解法就是从左到右遍历一遍,比较相邻的元素,把重复的元素从数组中删除,最后返回数组的长度就是答案。虽然这样做也能 AC,但是时间复杂度较高,代码比较简单,略。
第二种解法可以使用双指针。使用一个慢指针 slow 指向开头,然后使用一个快指针 fast 每次向后移动。当 slow 和 fast 指向的元素不同,slow 加 1,然后将 fast 指向的元素赋值给 slow 指向的元素。这样,数组遍历完毕后,前 slow + 1 个元素都是不同的元素,返回 slow + 1 就是答案。
举例:nums = 1,1,2,3
时间复杂度为 O(N),空间复杂度为 O(1)。
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就是前面不同元素的长度
这道题是给一个排序好的数组,通过修改原数组,使得每个元素最多只出现两次,把这些数(假设为 K 个)依次排到数组最前面,返回 K,要求使用 O(1) 的空间。
同上面的 Leetcode 80,这道题也可以使用双指针法求解:如果数组长度小于等于 2,则直接返回数组长度就是答案。否则,使用慢指针 slow 始终指向要改变的位置,使用快指针 fast 向后移动。刚开始,两指针都指向 nums2 的位置,每次,fast 都往后移动一位。如果发现 nums[slow-2] != nums[fast]
**,就将 numsfast 赋值给 numsslow, 然后 slow + 1 继续判断。最后遍历结束后,前 slow 个元素满足题意,返回 slow 就是答案。**
为什么 fast 要和 slow - 2 比较?以一个例子 nums = 0,0,0,1,2,2,3 说明:
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]
最大宽度坡。给一个数组 A,坡是元组 (i, j),其中 i < j 且 Ai <= Aj。坡的宽度为 j - i。找出 A 中坡的最大宽度,如果不存在,返回 0 。
首先看数据范围,肯定不能使用 O(n^2) 的暴力解法,pass。
方法1(Sort):
这道题的实际上是求这样一个问题:max(j - i),i < j and Ai <= Aj。类似于 Leetcode 【Math、DP】121. Best Time to Buy and Sell Stock 方法 1 的解法:在遍历的过程中,i_min 指向最小值,并更新 j - i_min 的最大值。但是这道题还有 Ai <= Aj 的限制,因此我们先要对数组,并且带上索引进行升序排序。
注意:升序排序虽然满足 Ai <= Aj,但是破坏了 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 = 6,8,2,2,1,5,3,ans = 0 更新结果
时间复杂度为 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(左右遍历法+双指针):
参考大牛的解题思路,做法很巧妙:
(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.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.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 分别指向 leftMini 和 rightMaxj(初始 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
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