2762

2762. Continuous Subarrays (Medium)

You are given a 0-indexed integer array nums. A subarray of nums is called continuous if:

• Let i, i + 1, ..., j be the indices in the subarray. Then, for each pair of indices i <= i1, i2 <= j, 0 <= |nums[i1] - nums[i2]| <= 2.

Return the total number of continuous subarrays.

A subarray is a contiguous non-empty sequence of elements within an array.

 

Example 1:

Input: nums = [5,4,2,4]
Output: 8
Explanation: 
Continuous subarray of size 1: [5], [4], [2], [4].
Continuous subarray of size 2: [5,4], [4,2], [2,4].
Continuous subarray of size 3: [4,2,4].
Thereare no subarrys of size 4.
Total continuous subarrays = 4 + 3 + 1 = 8.
It can be shown that there are no more continuous subarrays.

 

Example 2:

Input: nums = [1,2,3]
Output: 6
Explanation: 
Continuous subarray of size 1: [1], [2], [3].
Continuous subarray of size 2: [1,2], [2,3].
Continuous subarray of size 3: [1,2,3].
Total continuous subarrays = 3 + 2 + 1 = 6.

 

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109

Companies: Yahoo, Adobe, Google

Related Topics:
Array, Queue, Sliding Window, Heap (Priority Queue), Ordered Set, Monotonic Queue

Solution 1. Find Maximum Sliding Window + Monotonic Queue

// OJ: https://leetcode.com/problems/continuous-subarrays
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    long long continuousSubarrays(vector<int>& A) {
        long long ans = 0, N = A.size();
        deque<int> mn, mx;
        for (int i = 0, j = 0; j < N; ++j) {
            while (mx.size() && A[mx.back()] <= A[j]) mx.pop_back();
            mx.push_back(j);
            while (mn.size() && A[mn.back()] >= A[j]) mn.pop_back();
            mn.push_back(j);
            while (mn.size() && A[mx.front()] - A[mn.front()] > 2) {
                if (mx.front() == i) mx.pop_front();
                if (mn.front() == i) mn.pop_front();
                ++i;
            }
            ans += j - i + 1;
        }
        return ans;
    }
};