712173. Sum of subarray minimum
Here is a detailed Markdown blog post for the problem "Sum of subarray minimum":
Sum-of-Subarray-Minimum
Summary
Given an array of integers, find the sum of all possible subarrays' minimum values. This problem involves arrays and stack data structures.
Detailed Explanation
The key to solving this problem is using a stack-based approach. We'll iterate through the array from left to right and maintain a stack of indices. Each index represents the ending position of a subarray. When we encounter a new element, we pop elements from the stack that are smaller than the current element until the top of the stack is either empty or its element is greater than the current one.
For each popped index, calculate the sum of all subarrays' minimum values ending at that index and add it to our total sum. This is because for any subarray ending at the popped index, its minimum value will be either the current element (if there are no smaller elements to the left) or the smallest element in the stack.
Here's a step-by-step breakdown of the solution:
- Initialize an empty stack.
- Iterate through the array from left to right:
- For each element, pop elements from the stack that are smaller than the current element until the top of the stack is either empty or its element is greater than the current one.
- For each popped index, calculate the sum of all subarrays' minimum values ending at that index and add it to our total sum.
- The final answer will be the total sum calculated in step 2.
Time complexity analysis: The time complexity is O(n), where n is the size of the input array. This is because we're iterating through the array once and popping elements from the stack in a linear fashion.
Space complexity analysis: The space complexity is O(n) as well, since we need to store all indices in the stack.
Optimized Solutions
Java
public int sumOfSubarrayMinimum(int[] nums) {
int n = nums.length;
int sum = 0;
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) {
int top = stack.pop();
int left = stack.isEmpty() ? -1 : stack.peek();
sum += nums[top] * (i - left);
}
stack.push(i);
}
while (!stack.isEmpty()) {
int top = stack.pop();
int right = n;
sum += nums[top] * (right - i);
}
return sum;
}