Untitled
unknown
plain_text
10 months ago
2.5 kB
2
Indexable
Never
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; } }; */