Problem
Solution 0: Brute force [TLE]
Enumerate all subarrays, for each one, find min and max.
Time complexity: O(n3)
Space complexity: O(1)
Solution 1: Prefix min/max
We can use prefix technique to extend the array while keep tracking the min/max of the subarray.
Time complexity: O(n2)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// Author: Huahua class Solution { public: long long subArrayRanges(vector<int>& nums) { const int n = nums.size(); long long ans = 0; for (int i = 0; i < n; ++i) { int lo = nums[i]; int hi = nums[i]; for (int j = i + 1; j < n; ++j) { lo = min(lo, nums[j]); hi = max(hi, nums[j]); ans += (hi - lo); } } return ans; } }; |
Solution 2: Monotonic stack
This problem can be reduced to 花花酱 LeetCode 907. Sum of Subarray Minimums
Just need to run twice one for sum of mins and another for sum of maxs.
Time complexity: O(n)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Author: Huahua class Solution { public: long long subArrayRanges(vector<int>& nums) { const int n = nums.size(); auto sumOf = [&](function<bool(int, int)> op) { long long ans = 0; stack<int> s; for (long long i = 0; i <= n; ++i) { while (!s.empty() and (i == n or op(nums[s.top()], nums[i]))) { long long k = s.top(); s.pop(); long long j = s.empty() ? -1 : s.top(); ans += nums[k] * (i - k) * (k - j); } s.push(i); } return ans; }; return sumOf(less<int>()) - sumOf(greater<int>()); } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment