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>& heights) {
    const int n = heights.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, heights, i, sum);
      maxSum[i] = sum;
    }

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

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

    return ranges::max(maxSum);
  }

 private:
  long process(stack<int>& stack, const vector<int>& heights, int i, long sum) {
    while (stack.size() > 1 && heights[stack.top()] > heights[i]) {
      const int j = stack.top();
      stack.pop();
      // The last abs(j - stack.top()) heights are `heights[j]`.
      sum -= static_cast<long>(abs(j - stack.top())) * heights[j];
    }
    // Put abs(i - stack.top()) * heights[i] in `heights`.
    sum += static_cast<long>(abs(i - stack.top())) * heights[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
class Solution {
  public long maximumSumOfHeights(int[] heights) {
    final int n = heights.length;
    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, heights, i, sum);
      maxSum[i] = sum;
    }

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

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

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

  private long process(Deque<Integer> stack, int[] heights, int i, long sum) {
    while (stack.size() > 1 && heights[stack.peek()] > heights[i]) {
      int j = stack.pop();
      // The last abs(j - stack.peek()) heights are `heights[j]`.
      sum -= (long) Math.abs(j - stack.peek()) * heights[j];
    }
    // Put abs(i - stack.peek()) * heights[i] in `heights`.
    sum += (long) Math.abs(i - stack.peek()) * heights[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
class Solution:
  def maximumSumOfHeights(self, heights: list[int]) -> int:
    n = len(heights)
    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 heights[stack[-1]] > heights[i]:
        j = stack.pop()
        # The last abs(j - stack[-1]) heights are heights[j].
        summ -= abs(j - stack[-1]) * heights[j]
      # Put abs(i - stack[-1]) `maxHeight` in heights.
      summ += abs(i - stack[-1]) * heights[i]
      stack.append(i)
      return summ

    stack = [-1]
    summ = 0
    for i in range(len(heights)):
      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 - heights[i]

    return max(maxSum)