leetcode

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