2024-06-23 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge
|

Today I have done leetcode's June LeetCoding Challenge with cpp.

June LeetCoding Challenge 23

Description

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

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

 

Constraints:

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

Solution

class Solution {
public:
  int longestSubarray(vector<int>& nums, int limit) {
    deque<int> maxMonoQueue, minMonoQueue;
    int begin = 0;
    int answer = 0;
    for(int end = 0; end < nums.size(); ++end) {
      while(maxMonoQueue.size() && maxMonoQueue.back() < nums[end]) maxMonoQueue.pop_back();
      while(minMonoQueue.size() && minMonoQueue.back() > nums[end]) minMonoQueue.pop_back();
      maxMonoQueue.push_back(nums[end]);
      minMonoQueue.push_back(nums[end]);
      while(maxMonoQueue.size() && minMonoQueue.size() && maxMonoQueue.front() - minMonoQueue.front() > limit) {
        if(maxMonoQueue.front() == nums[begin]) maxMonoQueue.pop_front();
        if(minMonoQueue.front() == nums[begin]) minMonoQueue.pop_front();
        begin += 1;
      }

      answer = max(answer, end - begin + 1);
    }

    return answer;
  }
};
Algorithm