leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

2104.cpp (950B)

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