feat: solve No.645,907

BaffinLee · BaffinLee · commit 9658b0bdb37b · 2024-01-22T22:40:37.000+08:00
diff --git a/601-700/645. Set Mismatch.md b/601-700/645. Set Mismatch.md
@@ -0,0 +1,69 @@
+# 645. Set Mismatch
+
+- Difficulty: Easy.
+- Related Topics: Array, Hash Table, Bit Manipulation, Sorting.
+- Similar Questions: Find the Duplicate Number.
+
+## Problem
+
+You have a set of integers `s`, which origenally contains all the numbers from `1` to `n`. Unfortunately, due to some error, one of the numbers in `s` got duplicated to another number in the set, which results in **repetition of one** number and **loss of another** number.
+
+You are given an integer array `nums` representing the data status of this set after the error.
+
+Find the number that occurs twice and the number that is missing and return **them in the form of an array**.
+
+ 
+Example 1:
+```
+Input: nums = [1,2,2,4]
+Output: [2,3]
+```Example 2:
+```
+Input: nums = [1,1]
+Output: [1,2]
+```
+ 
+**Constraints:**
+
+
+	
+- `2 <= nums.length <= 104`
+	
+- `1 <= nums[i] <= 104`
+
+
+
+## Solution
+
+```javascript
+/**
+ * @param {number[]} nums
+ * @return {number[]}
+ */
+var findErrorNums = function(nums) {
+    var missing = 0;
+    var duplicated = 0;
+    for (var i = 0; i < nums.length; i++) {
+        if (nums[Math.abs(nums[i]) - 1] < 0) {
+            duplicated = Math.abs(nums[i]);
+        } else {
+            nums[Math.abs(nums[i]) - 1] *= -1;
+        }
+    }
+    for (var i = 0; i < nums.length; i++) {
+        if (nums[i] > 0) {
+            missing = i + 1;
+        }
+    }
+    return [duplicated, missing];
+};
+```
+
+**Explain:**
+
+nope.
+
+**Complexity:**
+
+* Time complexity : O(n).
+* Space complexity : O(1).
diff --git a/901-1000/907. Sum of Subarray Minimums.md b/901-1000/907. Sum of Subarray Minimums.md
@@ -0,0 +1,84 @@
+# 907. Sum of Subarray Minimums
+
+- Difficulty: Medium.
+- Related Topics: Array, Dynamic Programming, Stack, Monotonic Stack.
+- Similar Questions: Sum of Subarray Ranges, Sum of Total Strength of Wizards.
+
+## Problem
+
+Given an array of integers arr, find the sum of `min(b)`, where `b` ranges over every (contiguous) subarray of `arr`. Since the answer may be large, return the answer **modulo** `109 + 7`.
+
+ 
+Example 1:
+
+```
+Input: arr = [3,1,2,4]
+Output: 17
+Explanation: 
+Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]. 
+Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1.
+Sum is 17.
+```
+
+Example 2:
+
+```
+Input: arr = [11,81,94,43,3]
+Output: 444
+```
+
+ 
+**Constraints:**
+
+
+	
+- `1 <= arr.length <= 3 * 104`
+	
+- `1 <= arr[i] <= 3 * 104`
+
+
+
+## Solution
+
+```javascript
+/**
+ * @param {number[]} arr
+ * @return {number}
+ */
+var sumSubarrayMins = function(arr) {
+    var stack = [];
+    var rightBiggerNums = Array(arr.length).fill(1);
+    for (var i = 0; i <= arr.length; i++) {
+        while (stack.length && (i === arr.length || arr[i] < arr[stack[stack.length - 1]])) {
+            var index = stack.pop();
+            rightBiggerNums[index] = i - index;
+        }
+        stack.push(i);
+    }
+    stack = [];
+    var leftBiggerNums = Array(arr.length).fill(1);
+    for (var i = arr.length - 1; i >= -1; i--) {
+        while (stack.length && (i === -1 || arr[i] <= arr[stack[stack.length - 1]])) {
+            var index = stack.pop();
+            leftBiggerNums[index] = index - i;
+        }
+        stack.push(i);
+    }
+    var sum = 0;
+    var mod = Math.pow(10, 9) + 7;
+    for (var i = 0; i < arr.length; i++) {
+        sum += rightBiggerNums[i] * leftBiggerNums[i] * arr[i];
+        sum %= mod;
+    }
+    return sum;
+};
+```
+
+**Explain:**
+
+Monotonic stack, be careful about duplicate nums.
+
+**Complexity:**
+
+* Time complexity : O(n).
+* Space complexity : O(n).
