2919. Minimum Increment Operations to Make Array Beautiful Medium

1/**
2 * [2919] Minimum Increment Operations to Make Array Beautiful
3 *
4 * You are given a 0-indexed integer array nums having length n, and an integer k.
5 * You can perform the following increment operation any number of times (including zero):
6 * 
7 * 	Choose an index i in the range [0, n - 1], and increase nums[i] by 1.
8 * 
9 * An array is considered beautiful if, for any subarray with a size of 3 or more, its maximum element is greater than or equal to k.
10 * Return an integer denoting the minimum number of increment operations needed to make nums beautiful.
11 * A subarray is a contiguous non-empty sequence of elements within an array.
12 *  
13 * <strong class="example">Example 1:
14 * 
15 * Input: nums = [2,3,0,0,2], k = 4
16 * Output: 3
17 * Explanation: We can perform the following increment operations to make nums beautiful:
18 * Choose index i = 1 and increase nums[1] by 1 -> [2,4,0,0,2].
19 * Choose index i = 4 and increase nums[4] by 1 -> [2,4,0,0,3].
20 * Choose index i = 4 and increase nums[4] by 1 -> [2,4,0,0,4].
21 * 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].
22 * In all the subarrays, the maximum element is equal to k = 4, so nums is now beautiful.
23 * It can be shown that nums cannot be made beautiful with fewer than 3 increment operations.
24 * Hence, the answer is 3.
25 * 
26 * <strong class="example">Example 2:
27 * 
28 * Input: nums = [0,1,3,3], k = 5
29 * Output: 2
30 * Explanation: We can perform the following increment operations to make nums beautiful:
31 * Choose index i = 2 and increase nums[2] by 1 -> [0,1,4,3].
32 * Choose index i = 2 and increase nums[2] by 1 -> [0,1,5,3].
33 * The subarrays with a size of 3 or more are: [0,1,5], [1,5,3], [0,1,5,3].
34 * In all the subarrays, the maximum element is equal to k = 5, so nums is now beautiful.
35 * It can be shown that nums cannot be made beautiful with fewer than 2 increment operations.
36 * Hence, the answer is 2.
37 * 
38 * <strong class="example">Example 3:
39 * 
40 * Input: nums = [1,1,2], k = 1
41 * Output: 0
42 * Explanation: The only subarray with a size of 3 or more in this example is [1,1,2].
43 * The maximum element, 2, is already greater than k = 1, so we don't need any increment operation.
44 * Hence, the answer is 0.
45 * 
46 *  
47 * Constraints:
48 * 
49 * 	3 <= n == nums.length <= 10^5
50 * 	0 <= nums[i] <= 10^9
51 * 	0 <= k <= 10^9
52 * 
53 */
54pub struct Solution {}
55
56// problem: https://leetcode.com/problems/minimum-increment-operations-to-make-array-beautiful/
57// discuss: https://leetcode.com/problems/minimum-increment-operations-to-make-array-beautiful/discuss/?currentPage=1&orderBy=most_votes&query=
58
59// submission codes start here
60
61impl Solution {
62    pub fn min_increment_operations(nums: Vec<i32>, k: i32) -> i64 {
63        
64    }
65}
66
67// submission codes end
68
69#[cfg(test)]
70mod tests {
71    use super::*;
72
73    #[test]
74    fn test_2919() {
75    }
76}
77