Skip to content

2865. Beautiful Towers I 👍

  • Time: $O(n)$
  • Space: $O(n)$
 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
37
38
39
class Solution {
 public:
  long long maximumSumOfHeights(vector<int>& maxHeights) {
    const int n = maxHeights.size();
    vector<long> maxSum(n);  // maxSum[i] := the maximum sum with peak i

    stack<int> stack{{-1}};
    long summ = 0;

    for (int i = 0; i < n; ++i) {
      summ = process(stack, maxHeights, i, summ);
      maxSum[i] = summ;
    }

    stack = std::stack<int>{{n}};
    summ = 0;

    for (int i = n - 1; i >= 0; --i) {
      summ = process(stack, maxHeights, i, summ);
      maxSum[i] += summ - maxHeights[i];
    }

    return ranges::max(maxSum);
  }

 private:
  long process(stack<int>& stack, vector<int>& maxHeights, int i, long summ) {
    while (stack.size() > 1 && maxHeights[stack.top()] > maxHeights[i]) {
      int j = stack.top();
      stack.pop();
      // The last abs(j - stack.top()) heights are maxHeights[j].
      summ -= abs(j - stack.top()) * static_cast<long>(maxHeights[j]);
    }
    // Put abs(i - stack.top()) * maxHeights[i] in `heights`.
    summ += abs(i - stack.top()) * static_cast<long>(maxHeights[i]);
    stack.push(i);
    return summ;
  }
};

 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
37
class Solution {
  public long maximumSumOfHeights(List<Integer> maxHeights) {
    final int n = maxHeights.size();
    long[] maxSum = new long[n]; // maxSum[i] := the maximum sum with peak i

    Deque<Integer> stack = new ArrayDeque<>(List.of(-1));
    stack.push(-1);
    long summ = 0;

    for (int i = 0; i < n; ++i) {
      summ = process(stack, maxHeights, i, summ);
      maxSum[i] = summ;
    }

    stack = new ArrayDeque<>(List.of(n));
    summ = 0;

    for (int i = n - 1; i >= 0; --i) {
      summ = process(stack, maxHeights, i, summ);
      maxSum[i] += summ - maxHeights.get(i);
    }

    return Arrays.stream(maxSum).max().getAsLong();
  }

  private long process(Deque<Integer> stack, List<Integer> maxHeights, int i, long summ) {
    while (stack.size() > 1 && maxHeights.get(stack.peek()) > maxHeights.get(i)) {
      final int j = stack.pop();
      // The last abs(j - stack.peek()) heights are maxHeights.get(j).
      summ -= Math.abs(j - stack.peek()) * (long) maxHeights.get(j);
    }
    // Put abs(i - stack.peek()) `maxHeights.get(i)` in heights.
    summ += Math.abs(i - stack.peek()) * (long) maxHeights.get(i);
    stack.push(i);
    return summ;
  }
}

 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
class Solution:
  def maximumSumOfHeights(self, maxHeights: list[int]) -> int:
    n = len(maxHeights)
    maxSum = [0] * n  # maxSum[i] := the maximum sum with peak i

    def process(stack: list[int], i: int, summ: int) -> int:
      while len(stack) > 1 and maxHeights[stack[-1]] > maxHeights[i]:
        j = stack.pop()
        # The last abs(j - stack[-1]) heights are maxHeights[j].
        summ -= abs(j - stack[-1]) * maxHeights[j]
      # Put abs(i - stack[-1]) `maxHeight` in heights.
      summ += abs(i - stack[-1]) * maxHeights[i]
      stack.append(i)
      return summ

    stack = [-1]
    summ = 0
    for i in range(len(maxHeights)):
      summ = process(stack, i, summ)
      maxSum[i] = summ

    stack = [n]
    summ = 0
    for i in range(n - 1, -1, -1):
      summ = process(stack, i, summ)
      maxSum[i] += summ - maxHeights[i]

    return max(maxSum)