leetcode2104 子数组范围和

思路：

单调栈。

实现：

 1 class Solution
 2 {
 3 public:
 4     long long work(vector<int>& nums, bool flg)
 5     {
 6         int n = nums.size();
 7         vector<int> l(n, 0), r(n, 0);
 8         l[0] = -1; r[n - 1] = n;
 9         stack<int> st;
10         st.push(0);
11         for (int i = 1; i < n; i++)
12         {
13             if (flg) while (!st.empty() and nums[i] <= nums[st.top()]) st.pop();
14             else while (!st.empty() and nums[i] >= nums[st.top()]) st.pop();
15             if (!st.empty()) l[i] = st.top();
16             else l[i] = -1;
17             st.push(i);
18         }
19         while (!st.empty()) st.pop();
20         st.push(n - 1);
21         for (int i = n - 2; i >= 0; i--)
22         {
23             if (flg) while (!st.empty() and nums[i] < nums[st.top()]) st.pop();
24             else while (!st.empty() and nums[i] > nums[st.top()]) st.pop();
25             if (!st.empty()) r[i] = st.top();
26             else r[i] = n; 
27             st.push(i);
28         }
29         long long res = 0;
30         for (int i = 0; i < n; i++)
31         {
32             res += (r[i] - (long long)i) * (i - l[i]) * nums[i];
33         }
34         return res;
35     }
36     long long subArrayRanges(vector<int>& nums)
37     {
38         long long x = work(nums, false);
39         long long y = work(nums, true);
40         return x - y;
41     }
42 };