preface

It’s 11:00 p.m. Is HXDM in bed? Brush the question can’t sleep ah? If you can’t sleep, get up and watch the problem solving for a while. 🐶 🐶

Topic describes

1438. The longest continuous subarray whose absolute difference does not exceed the limit

Given an integer array nums and an integer limit, return the length of the longest continuous subarray in which the absolute difference between any two elements must be less than or equal to limit.

If no subarray exists, 0 is returned.

Example 1:

Input: nums = [8,2,4,7], limit = 4 [8] the biggest absolute difference | | 8-8 = 0 < = 4. [8, 2] the biggest absolute difference | 2 | = 8-6 > 4. 4-trichlorobenzene [8] the biggest absolute difference | 2 | = 8-6 > 4.,2,4,7 [8] the biggest absolute difference | 2 | = 8-6 > 4. [2] Biggest absolute difference | 2-2 | = 0 < = 4. [2, 4] biggest absolute difference | | 2-4 = 2 < = 4.,4,7 [2] the biggest absolute difference | 2-7 | = 5 > 4. [4] the biggest absolute difference | | 4-4 = 0 < = 4. [4, 7] biggest absolute difference 4-7 | | = 3 < = 4. [7] the biggest absolute difference | 7-7 | = 0 < = 4. Therefore, the largest array that satisfies the problem has a length of 2.Copy the code

Example 2:

Input: nums =,1,2,4,7,2 [10], limit = 5 output: 4: meet the question of the eldest son arrays are,4,7,2 [2], the biggest absolute difference | 2-7 | = 5 < = 5.Copy the code

Example 3:

Input: nums = [4,2,2, 4,4,2,2], limit = 0 Output: 3Copy the code

Tip:

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • 0 <= limit <= 10^9

Their thinking

Given an integer array nums and an integer limit, to return the length of the longest continuous subarray, the absolute difference between the two elements must be less than or equal to limit.

So we need to count the maximum and minimum values in the current window, so we can also use two monotonic queues to solve this problem.

Therefore, we use a monotonically increasing queue minQ to maintain the minimum and a monotonically decreasing queue maxQ to maintain the maximum.

Then we only need to calculate the difference between the queue heads of the two queues to know whether the current window meets the condition.

Then return the result.

The problem solving code

var longestSubArray = function(nums, limit) {
  let maxQ = [], minQ = [], i = 0;

  for (let a of nums) {
    while(maxQ.length > 0 && a > maxQ[maxQ.length - 1]) {
      maxQ.pop();
    }
    while(minQ.length > 0 && a < minQ[minQ.length - 1]) {
      minQ.pop();
    }
    maxQ.push(a);
    minQ.push(a);

    if (maxQ[0] - minQ[0] > limit) {
      if (maxQ[0] == nums[i]) {
        maxQ.shift();
      }
      if (minQ[0] == nums[i]) {
        minQ.shift();
      }
      i++;
    }
  }
  return nums.length - i;
}
Copy the code

Swipe questions and punch out records

Here is the previous swipe card records, you can have a look, if you have any different views and views or feel what is wrong, welcome to leave a message in the comment area! 🙏 🙏 🙏

[LeetCode0303 topic area and retrieval – array immutable] | punch brush

[LeetCode1200. Minimum absolute difference] | punch brush

[LeetCode0304 topic 2 d area and retrieval – matrix immutable] | punch brush

[LeetCode11 topic containers of most water] | punch brush

[LeetCode0338 topic bit count] | punch brush

[LeetCode209 topic length minimum subarray] | punch brush

[LeetCode236 topic in recent common ancestor of binary tree] | punch brush

[LeetCode141 topic circular linked list] | punch brush

[LeetCode53 topic most architectural sequence and] | punch brush

[LeetCode48 topic rotating images] | punch brush

[LeetCode155 topic minimum stack] | punch brush

[LeetCode1124 problem well, the longest period of a] | punch brush

[LeetCode274 problem H index] | punch brush

[LeetCode367 problem effective completely square number] | punch brush

[LeetCode1047 problem delete all adjacent duplicates of the string] | punch brush

[LeetCode160 topic cross linked list] | punch brush

conclusion

Come on! HXDM!!!!!! 💪 💪 💪

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign