跳转至

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 <= 106
  • 1 <= positions.length == directions.length <= 105
  • 0 <= positions[i] <= height
  • directions[i] 为 'U' 或 'D'。

解法

方法一

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def maxArea(self, height: int, positions: List[int], directions: str) -> int:
        delta = defaultdict(int)
        diff = res = 0
        for pos, dir in zip(positions, directions):
            res += pos
            if dir == "U":
                diff += 1
                delta[height - pos] -= 2
                delta[height * 2 - pos] += 2
            else:
                diff -= 1
                delta[pos] += 2
                delta[height + pos] -= 2
        ans = res
        pre = 0
        for cur, d in sorted(delta.items()):
            res += (cur - pre) * diff
            pre = cur
            diff += d
            ans = max(ans, res)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public long maxArea(int height, int[] positions, String directions) {
        Map<Integer, Integer> delta = new TreeMap<>();
        int diff = 0;
        long res = 0;
        for (int i = 0; i < positions.length; ++i) {
            int pos = positions[i];
            char dir = directions.charAt(i);
            res += pos;
            if (dir == 'U') {
                ++diff;
                delta.merge(height - pos, -2, Integer::sum);
                delta.merge(height * 2 - pos, 2, Integer::sum);
            } else {
                --diff;
                delta.merge(pos, 2, Integer::sum);
                delta.merge(height + pos, -2, Integer::sum);
            }
        }
        long ans = res;
        int pre = 0;
        for (var e : delta.entrySet()) {
            int cur = e.getKey();
            int d = e.getValue();
            res += (long) (cur - pre) * diff;
            pre = cur;
            diff += d;
            ans = Math.max(ans, res);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    long long maxArea(int height, vector<int>& positions, string directions) {
        map<int, int> delta;
        int diff = 0;
        long long res = 0;

        for (int i = 0; i < positions.size(); ++i) {
            int pos = positions[i];
            char dir = directions[i];
            res += pos;

            if (dir == 'U') {
                ++diff;
                delta[height - pos] -= 2;
                delta[height * 2 - pos] += 2;
            } else {
                --diff;
                delta[pos] += 2;
                delta[height + pos] -= 2;
            }
        }

        long long ans = res;
        int pre = 0;

        for (const auto& [cur, d] : delta) {
            res += static_cast<long long>(cur - pre) * diff;
            pre = cur;
            diff += d;
            ans = max(ans, res);
        }

        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
func maxArea(height int, positions []int, directions string) int64 {
    delta := make(map[int]int)
    diff := 0
    var res int64 = 0
    for i, pos := range positions {
        dir := directions[i]
        res += int64(pos)

        if dir == 'U' {
            diff++
            delta[height-pos] -= 2
            delta[height*2-pos] += 2
        } else {
            diff--
            delta[pos] += 2
            delta[height+pos] -= 2
        }
    }
    ans := res
    pre := 0
    keys := make([]int, 0, len(delta))
    for key := range delta {
        keys = append(keys, key)
    }
    sort.Ints(keys)
    for _, cur := range keys {
        d := delta[cur]
        res += int64(cur-pre) * int64(diff)
        pre = cur
        diff += d
        ans = max(ans, res)
    }
    return ans
}

评论