diff options
-rw-r--r-- | longest_cont_subarr_abs_diff.c | 42 | ||||
-rw-r--r-- | longest_cont_subarr_abs_diff.py | 41 |
2 files changed, 83 insertions, 0 deletions
diff --git a/longest_cont_subarr_abs_diff.c b/longest_cont_subarr_abs_diff.c new file mode 100644 index 0000000..e9c8a0f --- /dev/null +++ b/longest_cont_subarr_abs_diff.c @@ -0,0 +1,42 @@ +// 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to +// Limit +#include "leetcode.h" + +/* + * 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 subarrays is less than equal or equal to 'limit' + */ + +int longestSubarray(int *nums, int numsSize, int limit) { + int n = numsSize, r = 0, l = 0, ans = 0, m_front = 0, m_end = 0, _m_front = 0, + _m_end = 0; + int *m_queue = (int *)malloc(n * sizeof(int)); + int *_m_queue = (int *)malloc(n * sizeof(int)); + for (r = 0; r < n; r++) { + while (_m_end > _m_front && nums[r] < _m_queue[_m_end - 1]) + _m_end--; + while (m_end > m_front && nums[r] > m_queue[m_end - 1]) + m_end--; + _m_queue[_m_end++] = nums[r]; + m_queue[m_end++] = nums[r]; + while ((m_queue[m_front] - _m_queue[_m_front]) > limit) { + if (m_queue[m_front] == nums[l]) + m_front++; + if (_m_queue[_m_front] == nums[l]) + _m_front++; + l++; + } + ans = fmax(ans, r - l + 1); + } + free(m_queue), free(_m_queue); + return ans; +} + +int main() { + int n1[] = {8, 2, 4, 7}, n2[] = {10, 1, 2, 4, 7, 2}, + n3[] = {4, 2, 2, 2, 4, 4, 2, 2}; + printf("%d\n", longestSubarray(n1, ARRAY_SIZE(n1), 4)); // expect: 2 + printf("%d\n", longestSubarray(n2, ARRAY_SIZE(n2), 5)); // expect: 4 + printf("%d\n", longestSubarray(n3, ARRAY_SIZE(n3), 0)); // expect: 3 +} diff --git a/longest_cont_subarr_abs_diff.py b/longest_cont_subarr_abs_diff.py new file mode 100644 index 0000000..579a1b7 --- /dev/null +++ b/longest_cont_subarr_abs_diff.py @@ -0,0 +1,41 @@ +# 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to +# Limit +from collections import deque + +""" +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 subarrays is less than equal or equal to 'limit' +""" + + +class Solution(object): + def longestSubarray(self, nums, limit): + """ + :type nums: List[int] + :type limit: int + :rtype: int + """ + max_d, min_d = deque(), deque() + n = 0 + for i in nums: + while len(max_d) and i > max_d[-1]: + max_d.pop() + while len(min_d) and i < min_d[-1]: + min_d.pop() + max_d.append(i) + min_d.append(i) + if max_d[0] - min_d[0] > limit: + if max_d[0] == nums[n]: + max_d.popleft() + if min_d[0] == nums[n]: + min_d.popleft() + n += 1 + return len(nums) - n + + +if __name__ == "__main__": + obj = Solution() + print(obj.longestSubarray(nums=[8, 2, 4, 7], limit=4)) + print(obj.longestSubarray(nums=[10, 1, 2, 4, 7, 2], limit=5)) + print(obj.longestSubarray(nums=[4, 2, 2, 2, 4, 4, 2, 2], limit=0)) |