Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.5 kB
2
Indexable
class Solution {// MONOTONIC QUEUE
public:
    long long continuousSubarrays(vector<int>& nums) { 
        int r=0,l=0;
        long long ans=0;
        deque<int> maxQ;
        deque<int> minQ;

        while(r<nums.size()){
            while(!maxQ.empty() && maxQ.back()<nums[r]){
                maxQ.pop_back();
            }
            maxQ.push_back(nums[r]);
            while(!minQ.empty() && minQ.back()>nums[r]){
                minQ.pop_back();
            }
            minQ.push_back(nums[r]);

            while(maxQ.front()-minQ.front()>2){
                if(maxQ.front()==nums[l]) maxQ.pop_front();
                if(minQ.front()==nums[l]) minQ.pop_front();
                l++;
            }
            ans+=r-l+1;
            r++;
        }
        return ans;
    }
};




/* 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;
    }
};
 */
//we can't useheap in this problem ,we need to use monotonic queue(not stack) bcoz things dont get deleted easily frm heap

//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;
    }
};
 */