C语言基于StackADT计算可见未遮挡建筑数的代码问题排查与优化

问题分析与代码修正 #

你的代码逻辑核心是正确的，但存在可以简化的空间。先明确问题的核心逻辑：

• 对于当前建筑，其前方可见的未遮挡建筑数量，等于处理当前建筑前栈的大小（栈中保存的是之前所有未被后续建筑遮挡的建筑，这些建筑对当前建筑都是可见的）。
• 弹出栈中所有小于等于当前高度的元素，是为了维护一个单调递减栈，确保后续建筑能正确计算可见数量（这些被弹出的元素会被当前建筑遮挡，无法被后续建筑看到）。

错误排查 #

你的代码在示例用例中运行正确，若出现错误，大概率是StackADT的实现问题：

• 检查Push是否正确递增size
• 检查Pop是否正确递减size
• 确认Top和IsEmpty的逻辑无误

优化后的简洁代码 #

int DoSomething(StackADT s, int value) {
    int visible = s->size; // 处理当前建筑前的栈大小就是可见数量
    
    // 移除会被当前建筑遮挡的元素（为后续计算做准备）
    while (!IsEmpty(s) && Top(s) <= value) {
        Pop(s);
    }
    
    Push(s, value);
    return visible;
}

代码说明 #

1. 可见数量计算：处理当前建筑前，栈中保存的是所有未被之前建筑遮挡的建筑，这些建筑对当前建筑都是可见的，因此直接取栈的大小即可。
2. 维护单调栈：弹出所有小于等于当前高度的元素，因为这些元素会被当前建筑遮挡，后续建筑无法看到它们，无需保留在栈中。
3. 入栈当前建筑：将当前建筑加入栈，作为后续建筑的参考。

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