计算双向循环链表中相互可见山峰对数及重复计数修正问询

问题根源 #

你当前的暴力遍历逻辑会把每一对可见山峰（比如A和B）分别在「A作为标记、B作为目标」和「B作为标记、A作为目标」时各统计一次，本质是没有限定统计的唯一性，导致重复计数。

三种可行修正方法 #

1. 限定遍历方向，单次统计每对 #

遍历每个节点作为标记指针时，只朝一个固定方向（比如顺时针）遍历非相邻节点，且只遍历到标记指针的前一个节点（避免绕回自身）。这样每一对可见山峰只会被统计一次：

• 比如链表{5,2,2,4,3}，以5为标记时，只顺时针遍历2、2、4这几个非相邻节点（3是相邻节点，跳过），统计5和4的可见对；
• 当以4为标记时，顺时针遍历3、5、2，此时5和4的配对属于反向，不在当前遍历的统计范围内，不会重复计数。

2. 用哈希集合记录已统计的节点对 #

给每个节点分配唯一ID，每次统计到一对可见山峰时，生成排序后的ID组合（比如A的ID是0，B的ID是3，就存(0,3)），先检查这个组合是否已在集合中：

• 若不存在，计数+1并将组合加入集合；
• 若已存在，直接跳过。
  这种方式从记录层面避免了重复统计，逻辑简单直接。

3. 单调栈优化（高效避免重复） #

如果链表节点数量较多，暴力遍历O(n²)的复杂度太高，可以用单调栈把时间复杂度降到O(n)，且天然不会重复统计：

1. 先找到链表中的最高节点（多个最高的话任选一个当起点）；
2. 用单调栈维护递减的山峰高度序列，从最高节点开始顺时针遍历一圈；
3. 对每个节点：
   • 弹出栈中所有高度≤当前节点的元素，每弹出一个就计数一次可见对；
   • 若栈不为空，再计数一次（当前节点和栈顶元素可见）；
   • 将当前节点压入栈；
4. 遍历结束后，处理栈中剩余元素，补充最高节点和后续节点的可见关系，避免遗漏。

示例验证 #

以{5,2,2,4,3}为例，最终正确的可见对包括：

• 相邻对：(5,2)、(2,2)、(2,4)、(4,3)、(3,5)
• 非相邻对：(5,4)
  总共6对，用上述方法都能准确统计，不会重复计数。

内容的提问来源于stack exchange，提问作者Michelin_Boi