此题解采用动态规划和几何优化方法。初始阶段，它构建一个最大的DP数组，每个元素表示从起始到当前位置的最小浪费空间。随后，为了处理k次调整的问题，使用数据结构（如SkipList）来优化查找和更新操作，确保每次调整都是在最优的位置。在每一轮中，它尝试确定新的调整点，并计算从该点到下一个可能的调整点之间的最小浪费空间。最终，这种方法可以在给定调整次数的限制下，找到总浪费空间最小的策略。
时间复杂度: O(k * N^2)
空间复杂度: O(N)
class SkipList:
def __init__(self):
# 初始化头节点和尾节点
self.head = [None, [None]]
self.tail = [self.head]
def insert_back(self, val):
# 在跳表尾部插入新节点
new_node = [val, []]
self.tail[0][1][0] = new_node
new_node[1].append(None)
self.tail[0] = new_node
def query(self, val):
# 查询小于等于给定值的最大节点
curr = self.head
for i in range(len(self.tail) - 1, -1, -1):
while (node := curr[1][i]) and node[0][0][0] <= val * node[0][0][2]:
curr = curr[1][i]
return curr
def split(self, criteria):
# 根据给定条件分割跳表
new_list = SkipList()
curr = self.head
for i in range(len(self.tail) - 1, -1, -1):
while curr[1][i] and criteria(curr[1][i]):
curr = curr[1][i]
if curr[1][i] is not None:
if len(new_list.tail) <= i:
delta = i + 1 - len(new_list.tail)
new_list.head[1].extend([None] * delta)
new_list.tail.extend([new_list.head] * delta)
t = curr[1][i]
new_list.head[1][i] = t
new_list.tail[i] = self.tail[i]
curr[1][i] = None
self.tail[i] = curr
if i and curr is self.head:
self.tail.pop()
self.head[1].pop()
return new_list
def merge(self, new_list):
# 合并两个跳表
for i in range(min(len(self.tail), len(new_list.tail))):
if new_list.head[1][i] is not None:
t = self.tail[i]
t[1][i] = new_list.head[1][i]
self.tail[i] = new_list.tail[i]
for i in range(len(self.tail), len(new_list.tail)):
self.head[1].append(new_list.head[1][i])
self.tail.append(new_list.tail[i])
new_list.tail = [new_list.head]
new_list.head[1] = [None]
class Solution:
def minSpaceWastedKResizing(self, nums: List[int], k: int) -> int:
# 主函数使用动态规划求解最小浪费空间
N = len(nums)
dp = []
m = 0
for i, n in enumerate(nums, 1):
# 更新每个时间点的最大需求空间
if n > m:
m = n
dp.append(m * i)
dp2 = [None] * len(dp)
for j in range(k):
ranges = []
lines_arc = SkipList()
for i in range(j + 1, N):
new_arc = deque([(i - 1, dp[i - 1])])
new_L = nums[i]
while ranges and ranges[-1][1] <= new_L:
old_arc, _ = ranges.pop()
while True:
# 几何优化处理交叉和更新范围
p1 = old_arc[-1]
while len(new_arc) > 1:
p2, p3 = new_arc[0], new_arc[1]
if (p2[0] - p1[0]) * (p3[1] - p2[1]) - (p3[0] - p2[0]) * (p2[1] - p1[1]) > 0:
break
else:
new_arc.popleft()
p0, p2 = (old_arc[-2] if len(old_arc) > 1 else None), new_arc[0]
if p0 is None or (p1[0] - p0[0]) * (p2[1] - p1[1]) - (p2[0] - p1[0]) * (p1[1] - p0[1]) > 0:
new_arc = old_arc+new_arc
break
else:
old_arc.pop()
while len(new_arc) > 1:
p0, p1 = new_arc[0], new_arc[1]
if p1 and p0[1] - p0[0] * new_L >= p1[1] - p1[0] * new_L:
new_arc.popleft()
else:
break
ranges.append((new_arc, new_L))
x, y = new_arc[0]
b = y - x * new_L
new_list = lines_arc.split(lambda x: x[0][1] > new_L)
while new_list.tail[0] is not new_list.head:
removed_list = new_list.head[1][0][0][2]
if removed_list.tail[0] is removed_list.head:
break
new_list = removed_list.split(lambda x: x[0][1] > new_L)
lines_arc.merge(removed_list)
removed_list = lines_arc.split(lambda node: new_L * node[0][0][0] + b * node[0][0][2] > node[0][0][1])
if lines_arc.tail[0] is lines_arc.head:
xp = x
yp = y
q = 1
else:
(xp0, yp0, q0), k0, _ = lines_arc.tail[0][0]
b0 = (yp0 - k0 * xp0) // q0
q = k0 - new_L
xp = b - b0
yp = b * k0 - b0 * new_L
lines_arc.insert_back(((xp, yp, q), new_L, removed_list))
curr_node = lines_arc.query(i)
(xp0, yp0, q0), k0, _ = curr_node[0]
b0 = (yp0 - k0 * xp0) // q0
dp2[i] = k0 * i + b0
dp2, dp = dp, dp2
return dp[-1] - sum(nums)