3578. Count Partitions With Max-Min Difference at Most K Medium

1/**
2 * [3578] Count Partitions With Max-Min Difference at Most K
3 *
4 * You are given an integer array nums and an integer k. Your task is to partition nums into one or more non-empty contiguous segments such that in each segment, the difference between its maximum and minimum elements is at most k.
5 * Return the total number of ways to partition nums under this condition.
6 * Since the answer may be too large, return it modulo 10^9 + 7.
7 *  
8 * <strong class="example">Example 1:
9 * <div class="example-block">
10 * Input: <span class="example-io">nums = [9,4,1,3,7], k = 4</span>
11 * Output: <span class="example-io">6</span>
12 * Explanation:
13 * There are 6 valid partitions where the difference between the maximum and minimum elements in each segment is at most k = 4:
14 * 
15 * 	[[9], [4], [1], [3], [7]]
16 * 	[[9], [4], [1], [3, 7]]
17 * 	[[9], [4], [1, 3], [7]]
18 * 	[[9], [4, 1], [3], [7]]
19 * 	[[9], [4, 1], [3, 7]]
20 * 	[[9], [4, 1, 3], [7]]
21 * </div>
22 * <strong class="example">Example 2:
23 * <div class="example-block">
24 * Input: <span class="example-io">nums = [3,3,4], k = 0</span>
25 * Output: <span class="example-io">2</span>
26 * Explanation:
27 * There are 2 valid partitions that satisfy the given conditions:
28 * 
29 * 	[[3], [3], [4]]
30 * 	[[3, 3], [4]]
31 * </div>
32 *  
33 * Constraints:
34 * 
35 * 	2 <= nums.length <= 5 * 10^4
36 * 	1 <= nums[i] <= 10^9
37 * 	0 <= k <= 10^9
38 * 
39 */
40pub struct Solution {}
41
42// problem: https://leetcode.com/problems/count-partitions-with-max-min-difference-at-most-k/
43// discuss: https://leetcode.com/problems/count-partitions-with-max-min-difference-at-most-k/discuss/?currentPage=1&orderBy=most_votes&query=
44
45// submission codes start here
46
47impl Solution {
48    pub fn count_partitions(nums: Vec<i32>, k: i32) -> i32 {
49        0
50    }
51}
52
53// submission codes end
54
55#[cfg(test)]
56mod tests {
57    use super::*;
58
59    #[test]
60    fn test_3578() {
61    }
62}
63