题目重点：用单调栈提取可成为最高/次高的相邻支配关系，避免二次枚举连续子数组。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练次大按位置计，重复最大可使差0；无长度≥2子数组返回0。
- 数字为整数，可为负；输出差值集合的和，不是全部子数组差值总和。
解题路线
- 任意非零差由某子数组唯一最高值u和一个次高v产生。选择最靠近u的v，二者间所有值≤v，所以u是该v在对应方向遇到的首个严格更大值。只需收集这些候选差。
- 单调递减stack：当前value比栈顶大时弹栈并记录value-top，这是被弹值的最近更大右值；弹完仍有较大栈顶，记录top-value作为最近更大左值。
- 栈顶与value相等时，两者间没有更高点，构成合法Top Two相等子数组，记录0；合并相等栈项不影响非零差数值种类。
- 每个候选差都可由其两端间的子数组见证：中间值≤较小端，所以Top Two恰两端。反向由最近严格更大关系证明任何非零目标差都会出现，去重set便完整。
- 不能把相邻原数组差简单求和；更大值与次大值可以隔多个更小元素。也不能把每次弹栈差累加不去重，多个子数组可能共享同差。
- 如果正式题次大指第二个不同值，零差是否出现改变；本题求和时0不贡献，非零差仍可选最靠近最高点的次高构造见证。保留题目这一术语缺口。
手动走一遍
训练[5,1,3]子数组差为4、2、2，distinct={4,2}和6；[5,5,1]得到{0,4}和4。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def distinct_difference_sum(values):
"""All contiguous subarrays length >=2; top two positions, duplicates included."""
stack=[]
differences=set()
for value in values:
while stack and stack[-1] < value:
differences.add(value-stack.pop())
if stack:
differences.add(stack[-1]-value)
if stack[-1]==value:stack.pop()
stack.append(value)
return sum(differences)
复杂度
O(n)期望时间、O(n)stack与差集合；每值至多入出栈一次、产生O(1)记录。固定宽度减法与总和须核溢出。
易错点与追问
容易失分的边界
- 把不连续子序列当正文规则。
- 重复差直接累计。
- 只看原数组相邻两值。
继续深挖
- 要输出全部distinct差如何改？
- 要算所有子数组差总和为何不能同一算法？
- 次大不同值合同怎样证明非零见证？
