3835. Count Subarrays With Cost Less Than or Equal to K Medium

1/**
2 * [3835] Count Subarrays With Cost Less Than or Equal to K
3 *
4 * You are given an integer array nums, and an integer k.
5 * For any <span data-keyword="subarray-nonempty">subarray</span> nums[l..r], define its cost as:
6 * cost = (max(nums[l..r]) - min(nums[l..r])) * (r - l + 1).
7 * Return an integer denoting the number of subarrays of nums whose cost is less than or equal to k.
8 *  
9 * <strong class="example">Example 1:
10 * <div class="example-block">
11 * Input: <span class="example-io">nums = [1,3,2], k = 4</span>
12 * Output: <span class="example-io">5</span>
13 * Explanation:
14 * We consider all subarrays of nums:
15 * 
16 * 	nums[0..0]: cost = (1 - 1) * 1 = 0
17 * 	nums[0..1]: cost = (3 - 1) * 2 = 4
18 * 	nums[0..2]: cost = (3 - 1) * 3 = 6
19 * 	nums[1..1]: cost = (3 - 3) * 1 = 0
20 * 	nums[1..2]: cost = (3 - 2) * 2 = 2
21 * 	nums[2..2]: cost = (2 - 2) * 1 = 0
22 * 
23 * There are 5 subarrays whose cost is less than or equal to 4.
24 * </div>
25 * <strong class="example">Example 2:
26 * <div class="example-block">
27 * Input: <span class="example-io">nums = [5,5,5,5], k = 0</span>
28 * Output: <span class="example-io">10</span>
29 * Explanation:
30 * For any subarray of nums, the maximum and minimum values are the same, so the cost is always 0.
31 * As a result, every subarray of nums has cost less than or equal to 0.
32 * For an array of length 4, the total number of subarrays is (4 * 5) / 2 = 10.
33 * </div>
34 * <strong class="example">Example 3:
35 * <div class="example-block">
36 * Input: <span class="example-io">nums = [1,2,3], k = 0</span>
37 * Output: <span class="example-io">3</span>
38 * Explanation:
39 * The only subarrays of nums with cost 0 are the single-element subarrays, and there are 3 of them.
40 * </div>
41 *  
42 * Constraints:
43 * 
44 * 	1 <= nums.length <= 10^5
45 * 	1 <= nums[i] <= 10^9
46 * 	0 <= k <= 10^15
47 * 
48 */
49pub struct Solution {}
50
51// problem: https://leetcode.com/problems/count-subarrays-with-cost-less-than-or-equal-to-k/
52// discuss: https://leetcode.com/problems/count-subarrays-with-cost-less-than-or-equal-to-k/discuss/?currentPage=1&orderBy=most_votes&query=
53
54// submission codes start here
55
56impl Solution {
57    pub fn count_subarrays(nums: Vec<i32>, k: i64) -> i64 {
58        
59    }
60}
61
62// submission codes end
63
64#[cfg(test)]
65mod tests {
66    use super::*;
67
68    #[test]
69    fn test_3835() {
70    }
71}
72