Skip to content

3279. Maximum Total Area Occupied by Pistons πŸ”’

Description

There are several pistons in an old car engine, and we want to calculate the maximum possible area under the pistons.

You are given:

  • An integer height, representing the maximum height a piston can reach.
  • An integer array positions, where positions[i] is the current position of piston i, which is equal to the current area under it.
  • A string directions, where directions[i] is the current moving direction of piston i, 'U' for up, and 'D' for down.

Each second:

  • Every piston moves in its current direction 1 unit. e.g., if the direction is up, positions[i] is incremented by 1.
  • If a piston has reached one of the ends, i.e., positions[i] == 0 or positions[i] == height, its direction will change.

Return the maximum possible area under all the pistons.

 

Example 1:

Input: height = 5, positions = [2,5], directions = "UD"

Output: 7

Explanation:

The current position of the pistons has the maximum possible area under it.

Example 2:

Input: height = 6, positions = [0,0,6,3], directions = "UUDU"

Output: 15

Explanation:

After 3 seconds, the pistons will be in positions [3, 3, 3, 6], which has the maximum possible area under it.

 

Constraints:

  • 1 <= height <= 106
  • 1 <= positions.length == directions.length <= 105
  • 0 <= positions[i] <= height
  • directions[i] is either 'U' or 'D'.

Solutions

Solution 1

 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
}

Comments