Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
1.6 kB
1
Indexable
Never
class Solution {//MULTISET
public:
    long long continuousSubarrays(vector<int>& nums) {
        int rear=0;
        long long res=0;
        multiset<int>st;
        for(int f=0;f<nums.size();f++){
            st.insert(nums[f]);
            while(st.size()>1 && *st.rbegin()-*st.begin()>2){//*st.rbegin() gives the value at end of st
                st.erase(st.find(nums[rear]));
                rear++;
            }
            res+=f-rear+1;
        }
        return res;
    }
};


//MYSOL (not working)
/* class Solution {
public:
    long long continuousSubarrays(vector<int>& nums) {
        int s = nums.size();
        int j = 0;
        long long res = 0;
        
        while (j < s) {
            queue<int> q;
            priority_queue<int, vector<int>, greater<int>> min;
            priority_queue<int, vector<int>, less<int>> max;
            
            while (j < s && (max.empty() || nums[j] - max.top() < 2) && (min.empty() || nums[j] - min.top() < 2)) {
                q.push(nums[j]);
                max.push(nums[j]);
                min.push(nums[j]);
                j++;
                
                while (!q.empty() && (!max.empty() && nums[j] - max.top() >= 2 || !min.empty() && nums[j] - min.top() >= 2)) {
                    if (!max.empty() && q.front() == max.top()) max.pop();
                    if (!min.empty() && q.front() == min.top()) min.pop();
                    q.pop();
                }
            }
            res += q.size();
        }
        return res;
    }
};
 */