动态规划相关题目

1.队列中看得到最多学生人数的学生

学校里有 N 个学生要站成一列纵队。队伍里的每个学生只能看见站在他前面、并且身高比他高的学生。例如，有 5 个学生站成一队，身高从前到后分别为 9 7 3 4 8 1，第 3 个学生能看到前 2 个学生，第 6 个学生只能看到第 1 和第 5 个学生。要求：给定队列中从前到后每个人的身高，请你给出一个有效的算法，计算出哪个学生能够看到最多的人数。

要解决这个问题，我们需要一个算法来确定每个学生能够看到前面几个学生。具体来说，每个学生只能看到他前面且身高比他高的学生。我们可以使用一个栈来高效地解决这个问题。

算法分析

1. 使用栈：

   • 我们可以从队列的前面向后面遍历，并使用一个栈来维护当前能被看到的学生。
   • 对于每个学生，如果栈顶的学生比当前学生矮，那么当前学生可以看到栈顶的学生。因此，当前学生可以看到栈顶学生及其下面的所有学生。将当前学生的索引压入栈中。
   • 栈中的学生会按从高到矮的顺序排列，以确保在后续处理时能够快速判断新学生能看到多少个之前的学生。

2. 详细步骤：

   • 初始化一个空栈和一个数组visible_count用于记录每个学生能看到的学生数量。
   • 遍历学生队列：
     • 对于每个学生，从栈中弹出所有比当前学生矮的学生，因为这些学生不能被后来的学生看到。
     • 将当前学生的索引压入栈中。
     • 记录当前学生能看到的学生数量，即栈的大小。

3. 时间复杂度：

   • 每个学生最多进栈和出栈一次，因此时间复杂度是 (O(N))。

代码实现

def max_visible_students(heights):
    n = len(heights)
    stack = []
    visible_count = [0] * n

    for i in range(n):
        # 弹出所有比当前学生矮的学生
        while stack and heights[stack[-1]] <= heights[i]:
            stack.pop()
        # 当前学生能看到的学生数
        visible_count[i] = len(stack)
        # 当前学生入栈
        stack.append(i)

    # 找到能看到最多学生的那个学生的索引
    max_visible = max(visible_count)
    student_index = visible_count.index(max_visible)
    
    return student_index, max_visible

# 测试用例
heights = [9, 7, 3, 4, 8, 1]
index, max_visible = max_visible_students(heights)
print(f"第 {index+1} 个学生能看到最多的人数，为 {max_visible} 人")

证明最优子结构和重叠子问题

1. 最优子结构：

   • 对于每个学生，其能看到的学生数取决于他前面的学生的能见情况。这意味着问题可以分解成更小的子问题，每个子问题的解都可以合并得到最终问题的解。

2. 重叠子问题：

   • 在计算每个学生能看到的人数时，我们需要多次访问和比较同一个学生的身高。因此，有重叠的子问题。

综上所述，我们使用栈的解决方案具有最优子结构和重叠子问题性质，能够在 (O(N)) 时间内有效解决问题。