1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

Medium

Given an array of integers nums and an integer limit, return the size of the longest non-empty subarray such that the absolute difference between any two elements of this subarray is less than or equal to limit.

Example 1:

• Input: nums = [8,2,4,7], limit = 4
• Output: 2
• Explanation: All subarrays are:

  [8] with maximum absolute diff |8-8| = 0 <= 4.
  [8,2] with maximum absolute diff |8-2| = 6 > 4.
  [8,2,4] with maximum absolute diff |8-2| = 6 > 4.
  [8,2,4,7] with maximum absolute diff |8-2| = 6 > 4.
  [2] with maximum absolute diff |2-2| = 0 <= 4.
  [2,4] with maximum absolute diff |2-4| = 2 <= 4.
  [2,4,7] with maximum absolute diff |2-7| = 5 > 4.
  [4] with maximum absolute diff |4-4| = 0 <= 4.
  [4,7] with maximum absolute diff |4-7| = 3 <= 4.
  [7] with maximum absolute diff |7-7| = 0 <= 4.
  Therefore, the size of the longest subarray is 2.

Example 2:

• Input: nums = [10,1,2,4,7,2], limit = 5
• Output: 4
• Explanation: The subarray [2,4,7,2] is the longest since the maximum absolute diff is |2-7| = 5 <= 5.

Example 3:

• Input: nums = [4,2,2,2,4,4,2,2], limit = 0
• Output: 3

Example 4:

• Input: nums = [2,2,2,4,4,2,5,5,5,5,5,2], limit = 2
• Output: 6

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109
• 0 <= limit <= 109

Solution:

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $limit
     * @return Integer
     */
    function longestSubarray($nums, $limit) {
        $ans = 1;
        $minQ = new SplDoublyLinkedList();
        $maxQ = new SplDoublyLinkedList();

        for ($l = 0, $r = 0; $r < count($nums); ++$r) {
            while (!$minQ->isEmpty() && $minQ->top() > $nums[$r])
                $minQ->pop();
            $minQ->push($nums[$r]);
            while (!$maxQ->isEmpty() && $maxQ->top() < $nums[$r])
                $maxQ->pop();
            $maxQ->push($nums[$r]);
            while ($maxQ->bottom() - $minQ->bottom() > $limit) {
                if ($minQ->bottom() == $nums[$l])
                    $minQ->shift();
                if ($maxQ->bottom() == $nums[$l])
                    $maxQ->shift();
                ++$l;
            }
            $ans = max($ans, $r - $l + 1);
        }

        return $ans;
    }
}

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

• LinkedIn
• GitHub