LeetCode 솔루션 분류
2104. Sum of Subarray Ranges
본문
https://leetcode.com/problems/sum-of-subarray-ranges/
You are given an integer array nums. The range of a subarray of nums is the difference between the largest and smallest element in the subarray.
Return the sum of all subarray ranges of nums.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [1,2,3] Output: 4 Explanation: The 6 subarrays of nums are the following: [1], range = largest - smallest = 1 - 1 = 0 [2], range = 2 - 2 = 0 [3], range = 3 - 3 = 0 [1,2], range = 2 - 1 = 1 [2,3], range = 3 - 2 = 1 [1,2,3], range = 3 - 1 = 2 So the sum of all ranges is 0 + 0 + 0 + 1 + 1 + 2 = 4.
Example 2:
Input: nums = [1,3,3] Output: 4 Explanation: The 6 subarrays of nums are the following: [1], range = largest - smallest = 1 - 1 = 0 [3], range = 3 - 3 = 0 [3], range = 3 - 3 = 0 [1,3], range = 3 - 1 = 2 [3,3], range = 3 - 3 = 0 [1,3,3], range = 3 - 1 = 2 So the sum of all ranges is 0 + 0 + 0 + 2 + 0 + 2 = 4.
Example 3:
Input: nums = [4,-2,-3,4,1] Output: 59 Explanation: The sum of all subarray ranges of nums is 59.
Constraints:
1 <= nums.length <= 1000-109 <= nums[i] <= 109
Follow-up: Could you find a solution with O(n) time complexity?
관련자료
-
링크
댓글 2
Coffee님의 댓글
- 익명
- 작성일
class Solution {
public long subArrayRanges(int[] nums) {
// find max
// find min
int min = nums[0];
int max = nums[0];
long accSum = 0;
for(int i=0; i<nums.length; i++){
min = nums[i];
max = min;
for(int j=i+1; j<nums.length; j++){
max = Math.max(max, nums[j]);
min = Math.min(min, nums[j]);
accSum += (max - min);
}
}
return accSum;
}
}austin님의 댓글
- 익명
- 작성일
O(n) linear solution
class Solution {
public:
long long subArrayRanges(vector<int>& nums) {
auto check = [&nums](auto &s, auto r, auto cmp) {
long long ret = 0;
while(!s.empty() && (r == nums.size() || cmp(nums[s.top()], nums[r]))) {
auto m = s.top(); s.pop();
ret += (m - (s.empty() ? -1 :s.top())) * (r - m) * nums[m];
}
s.emplace(r);
return ret;
};
long long ret = 0LL;
stack<long long> ms, ls;
for(long long r = 0; r <= nums.size(); ++r) {
ret -= check(ls, r, greater<int>());
ret += check(ms, r, less<int>());
}
return ret;
}
};
