leetcode

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

0907.cpp (603B)

      1 class Solution {
      2     static const int MOD = 1e9 + 7;
      3 
      4   public:
      5     int sumSubarrayMins(const vector<int> &arr) {
      6         const int n = arr.size();
      7         stack<int> st;
      8 
      9         long long res = 0;
     10         for (int right = 0, mid, left; right <= n; right++) {
     11             while (!st.empty() && (right == n || arr[st.top()] > arr[right])) {
     12                 mid = st.top(), st.pop();
     13                 left = st.empty() ? -1 : st.top();
     14                 res = (res + (long long)arr[mid] * (right - mid) * (mid - left)) % MOD;
     15             }
     16             st.push(right);
     17         }
     18         return res;
     19     }
     20 };