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

Problem

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 <= 10^5
• 1 <= nums[i] <= 10^9
• 0 <= limit <= 10^9

Problem Statement

Given an integer array nums and an integer limit representing the restriction, return the length of the longest continuous subarray such that the absolute difference between any two elements in this subarray must be less than or equal to limit. If no subarray satisfies the condition, return 0.

Solution Approach

• The first idea that comes to mind is to use a sliding window to traverse the array once, sort each window, and take out the maximum and minimum values. The time complexity of traversing once with a sliding window is O(n), so whether the time complexity of this problem is efficient depends on the sorting algorithm. Since the data in two adjacent windows is related and only 2 pieces of data change (the data moved out of the left side of the window and the data moved into the right side of the window), there is no need to sort from scratch every time. Here, a binary search tree is used for sorting; adding and deleting elements has a time complexity of O(log n). The total time complexity of this method is O(n log n). The space complexity is O(n).
• Is there still room to further optimize the binary search tree approach? The answer is yes. The binary search tree maintains the ordered relationship of all nodes, but this relationship is redundant. This problem only needs to find the maximum and minimum values and does not need the ordered information of the other nodes. So using a binary search tree is overkill. It can be replaced with 2 monotonic queues: one maintains the maximum value in the window, and the other maintains the minimum value in the window. After this optimization, the time complexity is reduced to O(n), and the space complexity is O(n). See the code for the specific implementation.
• Problems about monotonic stacks also include Problem 42, Problem 84, Problem 496, Problem 503, Problem 739, Problem 856, Problem 901, Problem 907, Problem 1130, Problem 1425, and Problem 1673.

Code

package leetcode

func longestSubarray(nums []int, limit int) int {
	minStack, maxStack, left, res := []int{}, []int{}, 0, 0
	for right, num := range nums {
		for len(minStack) > 0 && nums[minStack[len(minStack)-1]] > num {
			minStack = minStack[:len(minStack)-1]
		}
		minStack = append(minStack, right)
		for len(maxStack) > 0 && nums[maxStack[len(maxStack)-1]] < num {
			maxStack = maxStack[:len(maxStack)-1]
		}
		maxStack = append(maxStack, right)
		if len(minStack) > 0 && len(maxStack) > 0 && nums[maxStack[0]]-nums[minStack[0]] > limit {
			if left == minStack[0] {
				minStack = minStack[1:]
			}
			if left == maxStack[0] {
				maxStack = maxStack[1:]
			}
			left++
		}
		if right-left+1 > res {
			res = right - left + 1
		}
	}
	return res
}