Welcome to Subscribe On Youtube

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

• Java
• C++
• Python
• Go
• TypeScript

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

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

• 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
  
  

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

• function maxArea(height: number, positions: number[], directions: string): number {}
  
  

All Problems

All Solutions