836. Rectangle Overlap

两个矩阵有重叠 <=> 他们在 x 与 y 轴上的投影也有重叠。因此问题转化为线段是否重叠 return x_overlap && y_overlap

overlap (left_of_a, right_of_a) (left_of_b, right_of_b) = 
    (max left_of_a left_of_b) < (min right_of_a right_of_b)

897. Increasing Order Search Tree

inorder traversal

907. Sum of Subarray Minimums

对于每一个元素 at i，如果我们知道它在最大哪个区间内是最小值，我们就能知道在最后的结果中该元素被计算了多少次

const prev = new Array(xs.length).fill(-1)
const next = new Array(xs.length).fill(xs.length)
// monotonic stack
const stack = [[-Infinity, -1]]
for (let i = 0; i < xs.length; i += 1) {
    while (stack[stack.length - 1][0] > xs[i]) {
        next[stack[stack.length - 1][1]] = i
        stack.pop()
    }
    prev[i] = stack[stack.length - 1][1]
    stack.push([xs[i], i])
}

对每个元素 at i, [prev[i], prev[i] + 1, ..., i, ..., next[i] - 1, next[i]]，其在区间 prev[i] + 1..next[i] 中是最小元素

• i 左侧有 lc = (i - 1) - (prev[i] + 1) + 1 = i - 1 - prev[i] 个元素小于 i
• i 右侧有 rc = (next[i] - 1) - (i + 1) + 1 = next[i] - 1 - i 个元素小于 i

可以得到这个区间所有的含位置 i 的 subarray 个数: (lc + 1) * (rc + 1)