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

Posted on | Edited on | Views:

https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/

Sliding Window)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
// Time Limit Exceeded
/*
class Solution {
    public int longestSubarray(int[] nums, int limit) {
        int len=nums.length;
        int maxNum=Integer.MIN_VALUE;
        int maxLen=0;
        for(int i=0;i<len;i++){
            for(int j=i;j<len;j++){
                if(maxAbs(i,j,nums)<=limit) {
                    maxLen=(j-i+1)>maxLen?(j-i+1):maxLen;
                }
            }
        }
       return maxLen; 
    }
    public int maxAbs(int l,int r, int[] nums){
        if(l==r) return 0;
        int maxNum=Integer.MIN_VALUE;
        for(int i=l;i<r;i++){
            for(int j=i+1;j<=r;j++){
                int rangeAbs=Math.abs(nums[i]-nums[j]);
                maxNum=rangeAbs>maxNum?rangeAbs:maxNum;
            }
        }
        return maxNum;
    }
}*/
public class lc1438 {

    public static int longestSubarray(int[] A, int limit) {
        // intuition to use Deque: 
        // to store the max and min of the curren range [l-r]
        // and the next range [l+1,r]
        Deque<Integer> maxd = new ArrayDeque<>();
        Deque<Integer> mind = new ArrayDeque<>();
        int l = 0, r;
        for (r = 0; r < A.length; ++r) {
            while (!maxd.isEmpty() && A[r] > maxd.peekLast()) maxd.pollLast(); // >=,wrong
            while (!mind.isEmpty() && A[r] < mind.peekLast()) mind.pollLast(); // <=,wrong
            maxd.addLast(A[r]);
            mind.addLast(A[r]);
            if (maxd.peek() - mind.peek() > limit) {
                if (maxd.peek() == A[l]) maxd.poll();
                if (mind.peek() == A[l]) mind.poll();
                ++l;
            }
        }
        return r - l;
    }

    // driver method
    public static void main(String[] args) {
        int[] A={10,1,2,4,7,2};
        int limit=5;
        System.out.println(longestSubarray(A, limit));
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// DP trial, failed
// class Solution {
//     public int longestSubarray(int[] nums, int limit) {
//         int len=nums.length;
//         int[][] dp=new int[len][len];
//         for(int i=0;i<len;i++){
//             dp[i][i]=1;
//             int min=nums[i],max=nums[i];
//             for(int j=i+1;j<len;j++){
//                 min=nums[j]<min?nums[j]:min;
//                 max=nums[j]>max?nums[j]:max;
//                 // dp[i][j]=Math.max(dp[i][j-1],Math.max(Math.abs(nums[j]-min),Math.abs(max-nums[j])));
//                 if(Math.max(Math.abs(nums[j]-min),Math.abs(max-nums[j]))<=limit) dp[i][j]=dp[i][j-1]+1;
//                 else dp[i][j]=dp[i][j-1];
//             }
//         }
        
//         int maxLen=0;
//         for(int i=0;i<len;i++){
//             for(int j=i;j<len;j++){
//                 maxLen=dp[i][j]>maxLen?dp[i][j]:maxLen;
//             }
//         }
//         return maxLen;
//     }
// }
0%