Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- public int sumSubarrayMins(int[] arr) {
- int len = arr.length;
- int[] left = new int[len];
- int[] right = new int[len];
- Stack<int[]> stack = new Stack<>();
- for(int i = 0 ; i < len ; i++){
- int count = 1;
- while( stack.size() > 0 && stack.peek()[0] >= arr[i]){
- int[] popped = stack.pop();
- count += popped[1];
- }
- stack.push(new int[]{arr[i],count,i});
- left[i] = count;
- }
- stack.clear();
- for(int i = len-1; i >= 0 ; i--){
- int count = 1;
- while( stack.size() > 0 && stack.peek()[0] > arr[i]){
- int[] popped = stack.pop();
- count += popped[1];
- }
- stack.push(new int[]{arr[i],count,i});
- right[i] = count;
- }
- long sum = 0;
- int mod = 1000000007;
- for(int i = 0 ; i < len ; i++){
- long temp = ((left[i] % mod )* 1L * (right[i] % mod)) % mod;
- temp = ((arr[i] % mod ) *1L* (temp % mod)) % mod;
- sum = (sum % mod+ temp % mod) % mod;
- }
- return (int)sum;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement