https://leetcode-cn.com/problems/max-chunks-to-make-sorted-ii/submissions/
思路
https://leetcode-solution.cn/solutionDetail?type=3&id=6&max_id=2
单调栈模版
https://lucifer.ren/blog/2020/11/03/monotone-stack/
代码
class Solution:
def maxChunksToSorted(self, arr: List[int]) -> int:
n = len(arr)
sorted_arr = sorted(arr)
preIndex = -1
res = 0
for i in range(len(arr)):
cnt1 = self.sort_chunk(arr, preIndex + 1, i)
cnt2 = self.sort_chunk(sorted_arr, preIndex + 1, i)
if self.judge(cnt1, cnt2):
res += 1
preIndex = i
return res
def sort_chunk(self, arr, i, j):
cnt = {}
for index in range(i, j + 1):
cnt[arr[index]] = cnt.get(arr[index], 0) + 1
return cnt
def judge(self, dic1, dic2):
for elem in dic1:
if elem not in dic2:
return False
if dic2[elem] != dic1[elem]:
return False
return True
优化
class Solution:
def maxChunksToSorted(self, arr: List[int]) -> int:
count = collections.defaultdict(int)
non_zero_cnt = 0
ans = 0
for a, b in zip(arr, sorted(arr)):
# 怎么区分记录的是a还是b,一个用+1,一个用-1
if count[a] == -1: # 说明sort数组前面有出现,diff-1
non_zero_cnt -= 1 # diff 从 -1 变成 0 ,non_zero_cnt 减一
if count[a] == 0: # 说明sort数组前面没有出现,diff+1
non_zero_cnt += 1 # diff 从 0 变成 1 ,non_zero_cnt 加一
count[a] += 1 # 记录a
if count[b] == 1: # 说明arr数组前面有出现,diff-1
non_zero_cnt -= 1 # diff 从 1 变成 0 ,non_zero_cnt 减一
if count[b] == 0: # 说明arr数组前面没出现,diff+1
non_zero_cnt += 1 # diff 从 0 变成 -1 ,non_zero_cnt 加一
count[b] -= 1 # 记录b
if non_zero_cnt == 0:
ans += 1 # ,non_zero_cnt 等于 0 表示 diff 全部相等
return ans
时间复杂度:瓶颈在于排序,因此时间复杂度为 O(NlogN),其中 N 为数组长度。
空间复杂度:使用了一个 counter,其大小是 N,因此空间复杂度为 O(N),其中 N 为数组长度。