-- TOC --
You are given a 0-indexed integer array nums having length n, and an integer k. You can perform the following increment operation any number of times (including zero): Choose an index i in the range [0, n - 1], and increase nums[i] by 1.
可以给数组任意位置元素做加法，每次+1。
An array is considered
beautifulif, for any subarray with a size of 3 or more, its maximum element is greater than or equal to k. Return an integer denoting the minimum number of increment operations needed to make nums beautiful. A subarray is a contiguous non-empty sequence of elements within an array.
这里漂亮数组的定义是：任意大于等于3的subarray，其最大元素都要大于或等于k。返回是数组变漂亮所执行+1操作的最小次数。
Example 1:
Input: nums = [2,3,0,0,2], k = 4
Output: 3
Explanation: We can perform the following increment operations to make nums beautiful:
Choose index i = 1 and increase nums[1] by 1 -> [2,4,0,0,2].
Choose index i = 4 and increase nums[4] by 1 -> [2,4,0,0,3].
Choose index i = 4 and increase nums[4] by 1 -> [2,4,0,0,4].
The subarrays with a size of 3 or more are: [2,4,0], [4,0,0], [0,0,4], [2,4,0,0], [4,0,0,4], [2,4,0,0,4].
In all the subarrays, the maximum element is equal to k = 4, so nums is now beautiful.
It can be shown that nums cannot be made beautiful with fewer than 3 increment operations.
Hence, the answer is 3.
Example 2:
Input: nums = [0,1,3,3], k = 5
Output: 2
Explanation: We can perform the following increment operations to make nums beautiful:
Choose index i = 2 and increase nums[2] by 1 -> [0,1,4,3].
Choose index i = 2 and increase nums[2] by 1 -> [0,1,5,3].
The subarrays with a size of 3 or more are: [0,1,5], [1,5,3], [0,1,5,3].
In all the subarrays, the maximum element is equal to k = 5, so nums is now beautiful.
It can be shown that nums cannot be made beautiful with fewer than 2 increment operations.
Hence, the answer is 2.
Example 3:
Input: nums = [1,1,2], k = 1
Output: 0
Explanation: The only subarray with a size of 3 or more in this example is [1,1,2].
The maximum element, 2, is already greater than k = 1, so we don't need any increment operation.
Hence, the answer is 0.
Constraints:
- 3 <= n == nums.length <= 105
- 0 <= nums[i] <= 109
- 0 <= k <= 109
此题是有点相对费解的，需要花点时间彻底理解题意。
list中每个元素存放的，不是最后的结果，而是：让当前位置的值>=k时并让整个array满足条件的最小+1数。这里很tricky，不容易想清楚，最终的结果，显然并不是list最后位置的值，而是最后3个位置的最小值！
class Solution:
def minIncrementOperations(self, nums: List[int], k: int) -> int:
"""
r = [max(k-nums[0],0),
max(k-nums[1],0),
max(k-nums[2],0)]
for i in range(3,len(nums)):
r.append(max(k-nums[i],0)+min(r[-3:]))
"""
r = [0 if k-nums[0]<=0 else k-nums[0],
0 if k-nums[1]<=0 else k-nums[1],
0 if k-nums[2]<=0 else k-nums[2]]
for i in range(3,len(nums)):
r.append((0 if k-nums[i]<=0 else k-nums[i])+min(r[-3:]))
return min(r[-3:])
本文链接：https://cs.pynote.net/ag/dp/202310302/
-- EOF --
-- MORE --