Meta Level4编程谜题：笛卡尔平面加号计数优化求助

问题描述 #

求解Meta的Level4编程谜题「Mathematical Art」：从笛卡尔平面原点出发，执行N次轴对齐笔画（方向为U/D/L/R，每次移动指定长度），统计满足上下左右四个方向均有颜料延伸的加号位置数量。

约束条件：

• 2 ≤ N ≤ 2,000,000
• 1 ≤ Lᵢ ≤ 1,000,000,000
• Dᵢ ∈ {U, D, L, R}

示例输入：

N = 9
L = [6, 3, 4, 5, 1, 6, 3, 3, 4]
D = ULDRULURD

预期输出：4

当前解法及问题 #

解法步骤 #

• 记录所有水平、垂直线段（包含端点及另一轴坐标）
• 将线段端点按从小到大排序
• 合并同一轴上相交或重叠的线段
• 提取线段内部有效坐标（排除端点）
• 求水平、垂直线段有效坐标的交集，数量即为加号数

代码实现 #

from typing import List

def getPlusSignCount(N: int, L: List[int], D: str) -> int:
    pos = [0, 0]
    x_lines = []
    y_lines = []
    plus_sign_count = 0

    for stroke in range(0, len(L)):
        if D[stroke] == "U":
            y_lines.append([[pos[1], pos[1] + L[stroke]], pos[0]])
            pos[1] = pos[1] + L[stroke]
        elif D[stroke] == "D":
            y_lines.append([[pos[1], pos[1] - L[stroke]], pos[0]])
            pos[1] = pos[1] - L[stroke]
        elif D[stroke] == "L":
            x_lines.append([[pos[0], pos[0] - L[stroke]], pos[1]])
            pos[0] = pos[0] - L[stroke]
        elif D[stroke] == "R":
            x_lines.append([[pos[0], pos[0] + L[stroke]], pos[1]])
            pos[0] = pos[0] + L[stroke]

    # 统一线段端点顺序（从小到大）
    for x in range(0, len(x_lines)):
        if x_lines[x][0][0] > x_lines[x][0][1]:
            x_lines[x] = [[x_lines[x][0][1], x_lines[x][0][0]], x_lines[x][1]]
    for y in range(0, len(y_lines)):
        if y_lines[y][0][0] > y_lines[y][0][1]:
            y_lines[y] = [[y_lines[y][0][1], y_lines[y][0][0]], y_lines[y][1]]


    # 合并相交或重叠的线段
    def merge_lines(lines):
        merged_lines = []
        for line in lines:
            for existing_line in merged_lines:
                if line[1] == existing_line[1]:
                    if line[0][1] >= existing_line[0][0] and line[0][0] <= existing_line[0][1]:
                        existing_line[0] = [min(line[0][0], existing_line[0][0]), max(line[0][1], existing_line[0][1])]
                        break
            else:
                merged_lines.append(line)
        return merged_lines

    x_lines = merge_lines(x_lines)
    y_lines = merge_lines(y_lines)

    # 提取线段内部有效坐标（排除端点）
    vaLid_xline_coords = set()
    valid_yline_coords = set()

    for line in x_lines:
        for i in range(line[0][0] + 1, line[0][1]):
            vaLid_xline_coords.add((i, line[1]))

    for line in y_lines:
        for i in range(line[0][0] + 1, line[0][1]):
            valid_yline_coords.add((line[1], i))

    # 计算交集数量
    for coordinate in vaLid_xline_coords:
        if coordinate in valid_yline_coords:
            plus_sign_count += 1

    return plus_sign_count

现存问题 #

当前代码通过28/33测试用例，剩余5个测试用例触发内存超限。此前的超时、答案错误问题已部分优化，但内存占用过高的核心问题仍未解决，需要进一步优化代码的内存与运行效率。

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