Skip to content

2866. Beautiful Towers II 👍

  • 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
40
41
class Solution {
 public:
  // Same as 2865. Beautiful Towers I
  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 sum = 0;

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

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

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

    return ranges::max(maxSum);
  }

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

 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 {
  // Same as 2865. Beautiful Towers I
  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));
    long sum = 0;

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

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

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

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

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

 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
class Solution:
  # Same as 2865. Beautiful Towers I
  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)