#3835

Count Subarrays With Cost Less Than or Equal to K

medium · 45.5% accepted · 144 likes · top 29%

array · queue · monotonic queue

⊣ practice⊣ open on leetcode ↗

Description

You are given an integer array nums, and an integer k.

For any subarray nums[l..r], define its cost as:

cost = (max(nums[l..r]) - min(nums[l..r])) * (r - l + 1).

Return an integer denoting the number of subarrays of nums whose cost is less than or equal to k.

Solution