Question

2865. Beautiful Towers I

中文文档

Description

You are given a 0-indexed array maxHeights of n integers.

You are tasked with building n towers in the coordinate line. The ith tower is built at coordinate i and has a height of heights[i].

A configuration of towers is beautiful if the following conditions hold:

1. 1 <= heights[i] <= maxHeights[i]
2. heights is a mountain array.

Array heights is a mountain if there exists an index i such that:

• For all 0 < j <= i, heights[j - 1] <= heights[j]
• For all i <= k < n - 1, heights[k + 1] <= heights[k]

Return _the maximum possible sum of heights of a beautiful configuration of towers_.

 

Example 1:

Input: maxHeights = [5,3,4,1,1]
Output: 13
Explanation: One beautiful configuration with a maximum sum is heights = [5,3,3,1,1]. This configuration is beautiful since:
- 1 <= heights[i] <= maxHeights[i]  
- heights is a mountain of peak i = 0.
It can be shown that there exists no other beautiful configuration with a sum of heights greater than 13.

Example 2:

Input: maxHeights = [6,5,3,9,2,7]
Output: 22
Explanation: One beautiful configuration with a maximum sum is heights = [3,3,3,9,2,2]. This configuration is beautiful since:
- 1 <= heights[i] <= maxHeights[i]
- heights is a mountain of peak i = 3.
It can be shown that there exists no other beautiful configuration with a sum of heights greater than 22.

Example 3:

Input: maxHeights = [3,2,5,5,2,3]
Output: 18
Explanation: One beautiful configuration with a maximum sum is heights = [2,2,5,5,2,2]. This configuration is beautiful since:
- 1 <= heights[i] <= maxHeights[i]
- heights is a mountain of peak i = 2. 
Note that, for this configuration, i = 3 can also be considered a peak.
It can be shown that there exists no other beautiful configuration with a sum of heights greater than 18.

 

Constraints:

• 1 <= n == maxHeights <= 103
• 1 <= maxHeights[i] <= 109

Solutions

Solution 1: Enumeration

We can enumerate each tower as the tallest tower, each time expanding to the left and right, calculating the height of each other position, and then accumulating to get the height sum $t$. The maximum of all height sums is the answer.

The time complexity is $O(n^2)$, and the space complexity is $O(1)$. Here, $n$ is the length of the array $maxHeights$.

class Solution:
  def maximumSumOfHeights(self, maxHeights: List[int]) -> int:
    ans, n = 0, len(maxHeights)
    for i, x in enumerate(maxHeights):
      y = t = x
      for j in range(i - 1, -1, -1):
        y = min(y, maxHeights[j])
        t += y
      y = x
      for j in range(i + 1, n):
        y = min(y, maxHeights[j])
        t += y
      ans = max(ans, t)
    return ans

class Solution {
  public long maximumSumOfHeights(List<Integer> maxHeights) {
    long ans = 0;
    int n = maxHeights.size();
    for (int i = 0; i < n; ++i) {
      int y = maxHeights.get(i);
      long t = y;
      for (int j = i - 1; j >= 0; --j) {
        y = Math.min(y, maxHeights.get(j));
        t += y;
      }
      y = maxHeights.get(i);
      for (int j = i + 1; j < n; ++j) {
        y = Math.min(y, maxHeights.get(j));
        t += y;
      }
      ans = Math.max(ans, t);
    }
    return ans;
  }
}

class Solution {
public:
  long long maximumSumOfHeights(vector<int>& maxHeights) {
    long long ans = 0;
    int n = maxHeights.size();
    for (int i = 0; i < n; ++i) {
      long long t = maxHeights[i];
      int y = t;
      for (int j = i - 1; ~j; --j) {
        y = min(y, maxHeights[j]);
        t += y;
      }
      y = maxHeights[i];
      for (int j = i + 1; j < n; ++j) {
        y = min(y, maxHeights[j]);
        t += y;
      }
      ans = max(ans, t);
    }
    return ans;
  }
};

func maximumSumOfHeights(maxHeights []int) (ans int64) {
  n := len(maxHeights)
  for i, x := range maxHeights {
    y, t := x, x
    for j := i - 1; j >= 0; j-- {
      y = min(y, maxHeights[j])
      t += y
    }
    y = x
    for j := i + 1; j < n; j++ {
      y = min(y, maxHeights[j])
      t += y
    }
    ans = max(ans, int64(t))
  }
  return
}

function maximumSumOfHeights(maxHeights: number[]): number {
  let ans = 0;
  const n = maxHeights.length;
  for (let i = 0; i < n; ++i) {
    const x = maxHeights[i];
    let [y, t] = [x, x];
    for (let j = i - 1; ~j; --j) {
      y = Math.min(y, maxHeights[j]);
      t += y;
    }
    y = x;
    for (let j = i + 1; j < n; ++j) {
      y = Math.min(y, maxHeights[j]);
      t += y;
    }
    ans = Math.max(ans, t);
  }
  return ans;
}

Solution 2: Dynamic Programming + Monotonic Stack

Solution 1 is sufficient to pass this problem, but the time complexity is relatively high. We can use "Dynamic Programming + Monotonic Stack" to optimize the enumeration process.

We define $f[i]$ to represent the height sum of the beautiful tower scheme with the last tower as the tallest tower among the first $i+1$ towers. We can get the following state transition equation:

$$ f[i]= \begin{cases} f[i-1]+heights[i],&\text{if } heights[i]\geq heights[i-1]\ heights[i]\times(i-j)+f[j],&\text{if } heights[i]<heights[i-1] \end{cases} $$

Where $j$ is the index of the first tower to the left of the last tower with a height less than or equal to $heights[i]$. We can use a monotonic stack to maintain this index.

We can use a similar method to find $g[i]$, which represents the height sum of the beautiful tower scheme from right to left with the $i$th tower as the tallest tower. The final answer is the maximum value of $f[i]+g[i]-heights[i]$.

The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array $maxHeights$.

class Solution:
  def maximumSumOfHeights(self, maxHeights: List[int]) -> int:
    n = len(maxHeights)
    stk = []
    left = [-1] * n
    for i, x in enumerate(maxHeights):
      while stk and maxHeights[stk[-1]] > x:
        stk.pop()
      if stk:
        left[i] = stk[-1]
      stk.append(i)
    stk = []
    right = [n] * n
    for i in range(n - 1, -1, -1):
      x = maxHeights[i]
      while stk and maxHeights[stk[-1]] >= x:
        stk.pop()
      if stk:
        right[i] = stk[-1]
      stk.append(i)
    f = [0] * n
    for i, x in enumerate(maxHeights):
      if i and x >= maxHeights[i - 1]:
        f[i] = f[i - 1] + x
      else:
        j = left[i]
        f[i] = x * (i - j) + (f[j] if j != -1 else 0)
    g = [0] * n
    for i in range(n - 1, -1, -1):
      if i < n - 1 and maxHeights[i] >= maxHeights[i + 1]:
        g[i] = g[i + 1] + maxHeights[i]
      else:
        j = right[i]
        g[i] = maxHeights[i] * (j - i) + (g[j] if j != n else 0)
    return max(a + b - c for a, b, c in zip(f, g, maxHeights))

class Solution {
  public long maximumSumOfHeights(List<Integer> maxHeights) {
    int n = maxHeights.size();
    Deque<Integer> stk = new ArrayDeque<>();
    int[] left = new int[n];
    int[] right = new int[n];
    Arrays.fill(left, -1);
    Arrays.fill(right, n);
    for (int i = 0; i < n; ++i) {
      int x = maxHeights.get(i);
      while (!stk.isEmpty() && maxHeights.get(stk.peek()) > x) {
        stk.pop();
      }
      if (!stk.isEmpty()) {
        left[i] = stk.peek();
      }
      stk.push(i);
    }
    stk.clear();
    for (int i = n - 1; i >= 0; --i) {
      int x = maxHeights.get(i);
      while (!stk.isEmpty() && maxHeights.get(stk.peek()) >= x) {
        stk.pop();
      }
      if (!stk.isEmpty()) {
        right[i] = stk.peek();
      }
      stk.push(i);
    }
    long[] f = new long[n];
    long[] g = new long[n];
    for (int i = 0; i < n; ++i) {
      int x = maxHeights.get(i);
      if (i > 0 && x >= maxHeights.get(i - 1)) {
        f[i] = f[i - 1] + x;
      } else {
        int j = left[i];
        f[i] = 1L * x * (i - j) + (j >= 0 ? f[j] : 0);
      }
    }
    for (int i = n - 1; i >= 0; --i) {
      int x = maxHeights.get(i);
      if (i < n - 1 && x >= maxHeights.get(i + 1)) {
        g[i] = g[i + 1] + x;
      } else {
        int j = right[i];
        g[i] = 1L * x * (j - i) + (j < n ? g[j] : 0);
      }
    }
    long ans = 0;
    for (int i = 0; i < n; ++i) {
      ans = Math.max(ans, f[i] + g[i] - maxHeights.get(i));
    }
    return ans;
  }
}

class Solution {
public:
  long long maximumSumOfHeights(vector<int>& maxHeights) {
    int n = maxHeights.size();
    stack<int> stk;
    vector<int> left(n, -1);
    vector<int> right(n, n);
    for (int i = 0; i < n; ++i) {
      int x = maxHeights[i];
      while (!stk.empty() && maxHeights[stk.top()] > x) {
        stk.pop();
      }
      if (!stk.empty()) {
        left[i] = stk.top();
      }
      stk.push(i);
    }
    stk = stack<int>();
    for (int i = n - 1; ~i; --i) {
      int x = maxHeights[i];
      while (!stk.empty() && maxHeights[stk.top()] >= x) {
        stk.pop();
      }
      if (!stk.empty()) {
        right[i] = stk.top();
      }
      stk.push(i);
    }
    long long f[n], g[n];
    for (int i = 0; i < n; ++i) {
      int x = maxHeights[i];
      if (i && x >= maxHeights[i - 1]) {
        f[i] = f[i - 1] + x;
      } else {
        int j = left[i];
        f[i] = 1LL * x * (i - j) + (j != -1 ? f[j] : 0);
      }
    }
    for (int i = n - 1; ~i; --i) {
      int x = maxHeights[i];
      if (i < n - 1 && x >= maxHeights[i + 1]) {
        g[i] = g[i + 1] + x;
      } else {
        int j = right[i];
        g[i] = 1LL * x * (j - i) + (j != n ? g[j] : 0);
      }
    }
    long long ans = 0;
    for (int i = 0; i < n; ++i) {
      ans = max(ans, f[i] + g[i] - maxHeights[i]);
    }
    return ans;
  }
};

func maximumSumOfHeights(maxHeights []int) (ans int64) {
  n := len(maxHeights)
  stk := []int{}
  left := make([]int, n)
  right := make([]int, n)
  for i := range left {
    left[i] = -1
    right[i] = n
  }
  for i, x := range maxHeights {
    for len(stk) > 0 && maxHeights[stk[len(stk)-1]] > x {
      stk = stk[:len(stk)-1]
    }
    if len(stk) > 0 {
      left[i] = stk[len(stk)-1]
    }
    stk = append(stk, i)
  }
  stk = []int{}
  for i := n - 1; i >= 0; i-- {
    x := maxHeights[i]
    for len(stk) > 0 && maxHeights[stk[len(stk)-1]] >= x {
      stk = stk[:len(stk)-1]
    }
    if len(stk) > 0 {
      right[i] = stk[len(stk)-1]
    }
    stk = append(stk, i)
  }
  f := make([]int64, n)
  g := make([]int64, n)
  for i, x := range maxHeights {
    if i > 0 && x >= maxHeights[i-1] {
      f[i] = f[i-1] + int64(x)
    } else {
      j := left[i]
      f[i] = int64(x) * int64(i-j)
      if j != -1 {
        f[i] += f[j]
      }
    }
  }
  for i := n - 1; i >= 0; i-- {
    x := maxHeights[i]
    if i < n-1 && x >= maxHeights[i+1] {
      g[i] = g[i+1] + int64(x)
    } else {
      j := right[i]
      g[i] = int64(x) * int64(j-i)
      if j != n {
        g[i] += g[j]
      }
    }
  }
  for i, x := range maxHeights {
    ans = max(ans, f[i]+g[i]-int64(x))
  }
  return
}

function maximumSumOfHeights(maxHeights: number[]): number {
  const n = maxHeights.length;
  const stk: number[] = [];
  const left: number[] = Array(n).fill(-1);
  const right: number[] = Array(n).fill(n);
  for (let i = 0; i < n; ++i) {
    const x = maxHeights[i];
    while (stk.length && maxHeights[stk.at(-1)] > x) {
      stk.pop();
    }
    if (stk.length) {
      left[i] = stk.at(-1);
    }
    stk.push(i);
  }
  stk.length = 0;
  for (let i = n - 1; ~i; --i) {
    const x = maxHeights[i];
    while (stk.length && maxHeights[stk.at(-1)] >= x) {
      stk.pop();
    }
    if (stk.length) {
      right[i] = stk.at(-1);
    }
    stk.push(i);
  }
  const f: number[] = Array(n).fill(0);
  const g: number[] = Array(n).fill(0);
  for (let i = 0; i < n; ++i) {
    const x = maxHeights[i];
    if (i && x >= maxHeights[i - 1]) {
      f[i] = f[i - 1] + x;
    } else {
      const j = left[i];
      f[i] = x * (i - j) + (j >= 0 ? f[j] : 0);
    }
  }
  for (let i = n - 1; ~i; --i) {
    const x = maxHeights[i];
    if (i + 1 < n && x >= maxHeights[i + 1]) {
      g[i] = g[i + 1] + x;
    } else {
      const j = right[i];
      g[i] = x * (j - i) + (j < n ? g[j] : 0);
    }
  }
  let ans = 0;
  for (let i = 0; i < n; ++i) {
    ans = Math.max(ans, f[i] + g[i] - maxHeights[i]);
  }
  return ans;
}