1438. 绝对差不超过限制的最长连续子数组

给你一个整数数组 nums ,和一个表示限制的整数 limit,请你返回最长连续子数组的长度,该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。

如果不存在满足条件的子数组,则返回 0 。

 

示例 1:

输入:nums = [8,2,4,7], limit = 4
输出:2 
解释:所有子数组如下:
[8] 最大绝对差 |8-8| = 0 <= 4.
[8,2] 最大绝对差 |8-2| = 6 > 4. 
[8,2,4] 最大绝对差 |8-2| = 6 > 4.
[8,2,4,7] 最大绝对差 |8-2| = 6 > 4.
[2] 最大绝对差 |2-2| = 0 <= 4.
[2,4] 最大绝对差 |2-4| = 2 <= 4.
[2,4,7] 最大绝对差 |2-7| = 5 > 4.
[4] 最大绝对差 |4-4| = 0 <= 4.
[4,7] 最大绝对差 |4-7| = 3 <= 4.
[7] 最大绝对差 |7-7| = 0 <= 4. 
因此,满足题意的最长子数组的长度为 2 。

示例 2:

输入:nums = [10,1,2,4,7,2], limit = 5
输出:4 
解释:满足题意的最长子数组是 [2,4,7,2],其最大绝对差 |2-7| = 5 <= 5 。

示例 3:

输入:nums = [4,2,2,2,4,4,2,2], limit = 0
输出:3

 

提示:

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

 

Method 1 sliding window

Seeking min/max for sliding window,O(n^2)

py

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        curMax=curMin=nums[0]
        subArray=[]
        for num in nums:
            if abs(curMax-curMin)<=limit and abs(num-curMax)<=limit and abs(num-curMin)<=limit:
                curMax=max(curMax,num)
                curMin=min(curMin,num)
                subArray.append(num)
            else:
                subArray.append(num)
                subArray.pop(0)
                curMax=max(subArray)
                curMin=min(subArray)
        return len(subArray)

Java

class Solution {
    public int longestSubarray(int[] nums, int limit) {
        int curMax=nums[0];
        int curMin=nums[0];
        Queue<Integer> subArray=new LinkedList<>();
        for(int num:nums){
            if(Math.abs(curMax-curMin)<=limit&&Math.abs(num-curMax)<=limit&&Math.abs(num-curMin)<=limit){
                curMax=Math.max(curMax,num);
                curMin=Math.min(curMin,num);
                subArray.offer(num);
            }
            else{
                subArray.offer(num);
                subArray.poll();
                curMax=Collections.max(subArray);
                curMin=Collections.min(subArray);
            }
        } 
        return subArray.size();
    }
}

Method 2 use priority queue or deque

Time O(N)
Space O(N)

py_0

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        res=1
        l=0
        maxd=deque()
        mind=deque()
        for r,num in enumerate(nums):
            # sliding window max/min
            while maxd and maxd[-1]<num:maxd.pop()
            while mind and mind[-1]>num:mind.pop()
            maxd.append(num)
            mind.append(num)
            # Pop out the front one by one
            while maxd and mind and maxd[0]-mind[0]>limit:
                if maxd[0]==nums[l]:maxd.popleft()
                if mind[0]==nums[l]:mind.popleft()
                l+=1
            res=max(res,r-l+1)
        return res

py_1

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        i=0
        maxd=deque()
        mind=deque()
        for num in nums:
            while maxd and maxd[-1]<num:maxd.pop()
            while mind and mind[-1]>num:mind.pop()
            maxd.append(num)
            mind.append(num)
            if maxd[0]-mind[0]>limit:
                if maxd[0]==nums[i]:maxd.popleft()
                if mind[0]==nums[i]:mind.popleft()
                i+=1
        return len(nums)-i

Java

class Solution {
    public int longestSubarray(int[] nums, int limit) {
        Deque<Integer> maxd = new ArrayDeque<>();
        Deque<Integer> mind = new ArrayDeque<>();
        int i = 0, j;
        for (j = 0; j < nums.length; j++) {
            while (!maxd.isEmpty() && maxd.peekLast() < nums[j]) maxd.pollLast();
            while (!mind.isEmpty() && mind.peekLast() > nums[j]) mind.pollLast();
            maxd.add(nums[j]);
            mind.add(nums[j]);
            if (maxd.peek() - mind.peek() > limit) {
                if (maxd.peek() == nums[i]) maxd.poll();
                if (mind.peek() == nums[i]) mind.poll();
                i++;
            }
        }
        return j - i;
    }
}

cpp

class Solution {
public:
    int longestSubarray(vector<int>& nums, int limit) {
        deque<int> maxd,mind;
        int i = 0, j;
        for (j = 0; j < nums.size(); j++) {
            while (!maxd.empty() && maxd.back() < nums[j]) maxd.pop_back();
            while (!mind.empty() && mind.back() > nums[j]) mind.pop_back();
            maxd.push_back(nums[j]);
            mind.push_back(nums[j]);
            if (maxd.front() - mind.front() > limit) {
                if (maxd.front() == nums[i]) maxd.pop_front();
                if (mind.front() == nums[i]) mind.pop_front();
                i++;
            }
        }
        return j - i;
    }
};

 

Method 3 binary search and remove

Keep an increasing list q.
Binary insert the current element.
If

q[-1]-q[0]>limit

,
binary search the position of  nums[i] and remove it from the list.

 

Time O(N^2)
Space O(N)

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        i=0
        q=[]
        for j in range(len(nums)):
            bisect.insort(q,nums[j])
            if q[-1]-q[0]>limit:
                q.pop(bisect.bisect(q,nums[i])-1)
                i+=1    
        return j-i+1

Method 4 use two heaps

Time O(NogN)
Space O(N)

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        maxq, minq = [], []
        res = i = 0
        for j, a in enumerate(nums):
            heapq.heappush(maxq, [-a, j])
            heapq.heappush(minq, [a, j])
            while -maxq[0][0] - minq[0][0] > limit:
                i = min(maxq[0][1], minq[0][1]) + 1
                while maxq[0][1] < i: heapq.heappop(maxq)
                while minq[0][1] < i: heapq.heappop(minq)
            res = max(res, j - i + 1)
        return res

Method 5 use TreeMap

Use one tree map can easily get the maximum and the minimum at the same time.
In java, we can use TreeMap to count elements.
In cpp, it suports multi treeset, that's even better.

 

Time O(NogN)
Space O(N)

 

Java

class Solution {
    public int longestSubarray(int[] nums, int limit) {
        int i=0,j;
        TreeMap<Integer,Integer> m=new TreeMap<>();
        for(j=0;j<nums.length;j++){
            m.put(nums[j],1+m.getOrDefault(nums[j],0));
            if(m.lastEntry().getKey()-m.firstEntry().getKey()>limit){
                m.put(nums[i],m.get(nums[i])-1);
                if(m.get(nums[i])==0)
                    m.remove(nums[i]);
                i++;
            }
        }
        return j-i;
    }
}

cpp

class Solution {
public:
    int longestSubarray(vector<int>& nums, int limit) {
        int i=0,j;
        multiset<int>m;
        for(j=0;j<nums.size();j++){
            m.insert(nums[j]);
            if(*m.rbegin()-*m.begin()>limit)
                m.erase(m.find(nums[i++]));
        }
        return j-i;
    }
};

 

 

reference:https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/discuss/609771/JavaC%2B%2BPython-Deques-O(N)

 

 
上一篇:WWDC 在即,苹果 App Store 曝光 Mind:与 watchOS 8 有关


下一篇:Elasticsearch Search Query(查询介绍)