3279：活塞占据的最大总区域（★★）

Ian

2024-09-11 约 534 字预计阅读 2 分钟次阅读

力扣第 3279 题

题目

一台旧车的引擎中有一些活塞，我们想要计算活塞下方的最大区域。

给定：

一个整数 height，表示活塞最大可到达的高度。
一个整数数组 positions，其中 positions[i] 是活塞 i 的当前位置，等于其下方的当前区域。
一个字符串 directions，其中 directions[i] 是活塞 i 的当前移动方向，'U' 表示向上，'D' 表示向下。

每一秒：

每个活塞向它的当前方向移动 1 单位。即如果方向向上，positions[i] 增加 1。
如果一个活塞到达了其中一个终点，即 positions[i] == 0 或 positions[i] == height，它的方向将会改变。

返回所有活塞下方的最大可能区域。

示例 1：

输入：height = 5, positions = [2,5], directions = "UD"

输出：7

解释：

当前活塞的位置下方区域最大。

示例 2：

输入：height = 6, positions = [0,0,6,3], directions = "UUDU"

输出：15

解释：

三秒后，活塞将会位于 [3, 3, 3, 6]，此时下方区域最大。

提示：

1 <= height <= 10⁶
1 <= positions.length == directions.length <= 10⁵
0 <= positions[i] <= height
directions[i] 为 'U' 或 'D'。

分析

运动以周期 height*2 循环，只需统计一个周期
维护每个时间点有多少往上、多少往下，即可维护面积的增量
每个活塞变向的时间是确定的，可以用差分

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution:
    def maxArea(self, height: int, positions: List[int], directions: str) -> int:
        d = defaultdict(int)
        for i,c in zip(positions,directions):
            if c=='U':
                d[0] += 1
                d[height-i] -= 2
                d[height*2-i] += 2
            else:
                d[0] -= 1
                d[i] += 2
                d[height+i] -= 2
        res = s = sum(positions)
        pre = 0
        diff = 0
        for x in sorted(d)+[height*2]:
            s += (x-pre)*diff
            res = max(res,s)
            diff += d[x]
            pre = x
        return res

934 ms

目录

3279：活塞占据的最大总区域（★★）

题目

分析

解答