子数组的最小值之和

记住口诀:维护值递增的下标栈,弹栈即结算贡献 arr[j] × left × right。下面每帧都在套它。

轮到 arr[0]=4(紫色)。它可能成为栈内元素的「右边界」:凡栈里值 ≥ 4 的下标,此刻弹出结算。当前 栈空。

把 arr[0]=4 自己压进栈(蓝色)。现在栈里下标对应的值严格递增,等着后面更小的元素来给它定右边界。

轮到 arr[1]=2(紫色)。它可能成为栈内元素的「右边界」:凡栈里值 ≥ 2 的下标,此刻弹出结算。当前 栈顶 arr[0]=4。

栈顶 arr[0]=4 的值 ≥ 2,弹出结算。它在绿色这段里当最小值:左边可选 1 个起点、右边可选 1 个终点,共 1×1=1 个子数组,贡献 4×1×1=4。累加和到 4。

把 arr[1]=2 自己压进栈(蓝色)。现在栈里下标对应的值严格递增,等着后面更小的元素来给它定右边界。

轮到 arr[2]=6(紫色)。它可能成为栈内元素的「右边界」:凡栈里值 ≥ 6 的下标,此刻弹出结算。当前 栈顶 arr[1]=2。

把 arr[2]=6 自己压进栈(蓝色)。现在栈里下标对应的值严格递增,等着后面更小的元素来给它定右边界。

轮到 arr[3]=1(紫色)。它可能成为栈内元素的「右边界」:凡栈里值 ≥ 1 的下标,此刻弹出结算。当前 栈顶 arr[2]=6。

栈顶 arr[2]=6 的值 ≥ 1,弹出结算。它在绿色这段里当最小值:左边可选 1 个起点、右边可选 1 个终点,共 1×1=1 个子数组,贡献 6×1×1=6。累加和到 10。

栈顶 arr[1]=2 的值 ≥ 1,弹出结算。它在绿色这段里当最小值:左边可选 2 个起点、右边可选 2 个终点,共 2×2=4 个子数组,贡献 2×2×2=8。累加和到 18。

把 arr[3]=1 自己压进栈(蓝色)。现在栈里下标对应的值严格递增,等着后面更小的元素来给它定右边界。

轮到 arr[4]=5(紫色)。它可能成为栈内元素的「右边界」:凡栈里值 ≥ 5 的下标,此刻弹出结算。当前 栈顶 arr[3]=1。

把 arr[4]=5 自己压进栈(蓝色)。现在栈里下标对应的值严格递增,等着后面更小的元素来给它定右边界。

轮到 arr[5]=3(紫色)。它可能成为栈内元素的「右边界」:凡栈里值 ≥ 3 的下标,此刻弹出结算。当前 栈顶 arr[4]=5。

栈顶 arr[4]=5 的值 ≥ 3,弹出结算。它在绿色这段里当最小值:左边可选 1 个起点、右边可选 1 个终点,共 1×1=1 个子数组,贡献 5×1×1=5。累加和到 23。

把 arr[5]=3 自己压进栈(蓝色)。现在栈里下标对应的值严格递增,等着后面更小的元素来给它定右边界。

轮到 arr[6]=7(紫色)。它可能成为栈内元素的「右边界」:凡栈里值 ≥ 7 的下标,此刻弹出结算。当前 栈顶 arr[5]=3。

把 arr[6]=7 自己压进栈(蓝色)。现在栈里下标对应的值严格递增,等着后面更小的元素来给它定右边界。

轮到 arr[7]=2(紫色)。它可能成为栈内元素的「右边界」:凡栈里值 ≥ 2 的下标,此刻弹出结算。当前 栈顶 arr[6]=7。

栈顶 arr[6]=7 的值 ≥ 2,弹出结算。它在绿色这段里当最小值:左边可选 1 个起点、右边可选 1 个终点,共 1×1=1 个子数组,贡献 7×1×1=7。累加和到 30。

栈顶 arr[5]=3 的值 ≥ 2,弹出结算。它在绿色这段里当最小值:左边可选 2 个起点、右边可选 2 个终点,共 2×2=4 个子数组,贡献 3×2×2=12。累加和到 42。

把 arr[7]=2 自己压进栈(蓝色)。现在栈里下标对应的值严格递增,等着后面更小的元素来给它定右边界。

数组扫完了,栈里还剩 2 个下标没结算。补一个虚拟的「值 0 哨兵」当统一右边界,0 比谁都小,能把它们全部逼出来。

栈顶 arr[7]=2 的值 ≥ 哨兵 0,弹出结算。它在绿色这段里当最小值:左边可选 4 个起点、右边可选 1 个终点,共 4×1=4 个子数组,贡献 2×4×1=8。累加和到 50。

栈顶 arr[3]=1 的值 ≥ 哨兵 0,弹出结算。它在绿色这段里当最小值:左边可选 4 个起点、右边可选 5 个终点,共 4×5=20 个子数组,贡献 1×4×5=20。累加和到 70。

每个元素都被弹栈结算过一次,各自当最小值时的贡献全部累加,最终答案 70。每个下标只入栈、出栈各一次,整体 O(n)。

边界先想清:单元素、含重复值、严格递减都能用同一套贡献法覆盖。

面试常追问退化场景与「改求最大值之和」的对称变形。