leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

2104.cpp (950B)

0 class Solution { 1 public: 2 long long subArrayRanges(const vector<int> &nums) { 3 const int n = nums.size(); 4 long long res = 0; 5 stack<int> st; 6 7 for (int right = 0, mid, left; right <= n; right++) { 8 while (!st.empty() && (right == n || nums[st.top()] >= nums[right])) { 9 mid = st.top(), st.pop(); 10 left = st.empty() ? -1 : st.top(); 11 res -= (long long)nums[mid] * (right - mid) * (mid - left); 12 } 13 st.push(right); 14 } 15 16 st.pop(); 17 for (int right = 0, mid, left; right <= n; right++) { 18 while (!st.empty() && (right == n || nums[st.top()] <= nums[right])) { 19 mid = st.top(), st.pop(); 20 left = st.empty() ? -1 : st.top(); 21 res += (long long)nums[mid] * (right - mid) * (mid - left); 22 } 23 st.push(right); 24 } 25 26 return res; 27 } 28 };