README_EN.md

comments	difficulty	edit_url	tags
true	Hard	https://github.com/doocs/leetcode/edit/main/solution/3200-3299/3279.Maximum%20Total%20Area%20Occupied%20by%20Pistons/README_EN.md	Array Hash Table String Counting Prefix Sum Simulation

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

Python3

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

Java

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;
    }
}

C++

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;
    }
};

Go

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
}