已知诚实猴子数量超n/2，如何设计算法找出全部诚实猴子？

该问题核心基于「诚实猴数量严格大于总数1/2」的前提条件，最多通过2n-2次询问即可识别出所有诚实猴，分为两个执行阶段：

阶段1：确定1只100%可信的诚实猴 #

我们用栈结构存储候选诚实猴，按顺序遍历所有猴子执行以下操作：

• 若栈为空，直接将当前遍历到的猴子压入栈
• 若栈不为空，询问栈顶猴子「当前遍历到的猴子是不是诚实猴」：
  • 若得到的回答为是：将当前猴子压入栈
  • 若得到的回答为否：将栈顶猴子弹出栈，同时丢弃当前遍历到的猴子
    遍历结束后，栈中剩余的最后一只猴子一定是诚实猴。

逻辑验证：每次我们丢弃一对猴子时，只有两种可能：要么其中一个是诚实猴一个是不可靠猴，要么两个都是不可靠猴。无论哪种情况，丢弃的诚实猴数量都不会超过丢弃的不可靠猴数量，诚实猴占多数的特性始终保持，最终剩下的候选者必然属于多数派的诚实猴。

阶段2：批量验证所有猴子的身份 #

用阶段1得到的确定诚实猴，挨个询问它「剩下的每一只猴子是不是诚实猴」，回答为是即为诚实猴，回答为否即为不可靠猴。

边界情况&复杂度说明 #

• 当n=1时，唯一的猴子直接判定为诚实猴
• 整个过程最多需要 (n-1) + (n-1) = 2n-2 次询问，时间复杂度为O(n)

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