给定一个长度为 n 的数组 nums ,算出他所有的 min(sub) 之和,其中 sub 指数组 nums 的所有连续子数组 , min(sub) 指子数组的最小值。
数据范围: ,数组中的值满足 ,由于结果可能非常大,所以返回结果对 取模的结果
[3,1,2,4,5]
30
子数组有 3、1、2、4、5、(3,1)、(3,2)、(3,4)、(3,5)、(1,2)、(1,4)、(1,5)、(2,4)、(2,5)、(4,5)、(3,1,2)、(3,1,4)、(3,1,5)、(3,2,4)、(3,4,5)、(1,2,4)、(1,2,5)、(2,4,5)、(3,1,2,4)、(3,1,2,5)、(3,2,4,5)、(1,2,4,5) 其最小值和是 30
public int sumSubarr (ArrayList<Integer> nums) { int[] arr = nums.stream().mapToInt(Integer::valueOf).toArray(); // write code here int n = arr.length; long res = 0; int mod = 1000000007; Stack<Integer> stack = new Stack<>(); for (int i = 0; i <= n; i++) { // 当发现较小的元素时 while (!stack.isEmpty() && (i == n || arr[stack.peek()] > arr[i])) { int idx = stack.pop(); // 弹出并处理 // idx 左边的元素, peek 到 idx 肯定都比 idx 大,否则不会被 pop 掉 int left = idx - (stack.isEmpty() ? -1 : stack.peek()); int right = i - idx; res += (long) arr[idx] * left * right; res %= mod; } stack.push(i); } return (int) res; }问: arr[i] 是 left 和 right + 1范围内的最小值,为何不用它计算最终结果
# -*- coding: utf-8 -*- # # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param nums int整型一维数组 # @return int整型 # class Solution: """ 题目: https://www.nowcoder.com/practice/a7401d0dd4ec4071a31fd434e150bcc2?tpId=196&tqId=40517&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=3&tags=&title= 参考: https://leetcode.cn/problems/sum-of-subarray-minimums/solution/zi-shu-zu-de-zui-xiao-zhi-zhi-he-by-leetcode/ 算法: 对于每个 j,考虑所有子序列 [i, j] 的最小值。想法是每当我们增加 j,这些最小值可能会有关联,事实上,min(A[i:j+1]) = min(A[i:j], A[j+1])。 我们维护最小值栈stack,stack中存储的元素为(x, c),表示以x为结尾且x为最小值的区间个数,stack按照x单调递增。枚举区间右端点j,弹出栈中 x >= y的元素,因为这些以x结尾且以x为最小值的区间,尾部追加y之后,变成以y结尾且以y为最小值的区间了。另外我们使用Sum来记录以当前元素y结尾的所有区间的最小值之和。 复杂度: 时间复杂度:O(n) 空间复杂度:O(n) """ def sumSubarr(self, nums): # write code here MOD = 10 ** 9 + 7 ans, Sum, stack = 0, 0, [] for j, y in enumerate(nums): count = 1 while stack and stack[-1][0] >= y: x, c = stack.pop() # 以元素x结尾的区间个数为c,现在我们将元素y作为这些区间的尾部,也就是之前c个以元素x为最小值的区间 变为 以元素y作为最小值的区间 count += c Sum -= x * c # dot始终记录以当前元素y结尾的所有区间的最小值之和 stack.append((y, count)) # count表示以元素y结尾且y作为区间最小值的区间个数 Sum += y * count ans += Sum # 累加以y结尾的所有区间的最小值之和 return ans % MOD if __name__ == "__main__": sol = Solution() # nums = [3, 1, 2, 4, 5] # nums = [3, 1, 2, 4] # nums = [11, 81, 94, 43, 3] nums = [1, 2] # nums = [3, 2, 1] res = sol.sumSubarr(nums) print res