Leetcode 2866: Beautiful Towers II
You are given an array maxHeights of n integers. Your task is to build n towers in the coordinate line where the height of the i-th tower is between 1 and maxHeights[i]. The configuration is beautiful if the heights form a mountain array, where heights increase to a peak and then decrease afterward. Return the maximum possible sum of the heights of a beautiful tower configuration.
Problem
Approach
Steps
Complexity
Input: The input consists of an array of integers representing the maximum heights of the towers. You need to find a configuration of towers where the heights form a mountain shape.
Example: maxHeights = [3, 5, 4, 1, 6]
Constraints:
• 1 <= n <= 10^5
• 1 <= maxHeights[i] <= 10^9
Output: Return the maximum sum of the heights of the towers in a valid mountain configuration.
Example: For input maxHeights = [3, 5, 4, 1, 6], the output is 14.
Constraints:
Goal: The goal is to find the maximum sum of tower heights such that the arrangement forms a valid mountain shape.
Steps:
• For each possible peak, calculate the sum of the heights of the non-decreasing and non-increasing parts of the mountain array.
• Iterate through the array to compute the possible configurations and find the one with the maximum sum.
Goal: The solution must handle up to 100,000 towers efficiently and accommodate heights up to 10^9.
Steps:
• 1 <= n <= 10^5
• 1 <= maxHeights[i] <= 10^9
Assumptions:
• The array will not be empty and will contain at least one tower.
• Input: For input maxHeights = [3, 5, 4, 1, 6], the output is 14.
• Explanation: The configuration heights = [3, 4, 4, 1, 2] is a valid mountain where the sum of heights is maximized.
Approach: We will compute the maximum sum of the heights by iterating through all possible peaks and adjusting the tower heights accordingly.
Observations:
• To form a mountain array, we need to consider the non-decreasing and non-increasing subsequences.
• The sum of the tower heights must be maximized while respecting the maximum height constraints.
• The challenge is finding an efficient way to calculate the sum for each possible peak.
Steps:
• For each possible peak, calculate the sum of the heights in the non-decreasing and non-increasing sequences.
• Track the maximum sum encountered during the iteration.
Empty Inputs:
• The input array will never be empty as per the constraints.
Large Inputs:
• Ensure the solution handles large arrays efficiently (n up to 100,000).
Special Values:
• If all towers have the same maximum height, any configuration with a peak in the middle will form a valid mountain.
Constraints:
• The solution must respect the maximum height constraints while maximizing the sum.
long long maximumSumOfHeights(vector<int>& A) {
int n = A.size();
vector<long long> left(n), stack = {-1};
long long res = 0, cur = 0;
for (int i = 0; i < n; i++) {
while (stack.size() > 1 && A[stack.back()] > A[i]) {
int j = stack.back();
stack.pop_back();
cur -= 1L * (j - stack.back()) * A[j];
}
cur += 1L * (i - stack.back()) * A[i];
stack.push_back(i);
left[i] = cur;
}
stack = {n};
cur = 0;
for (int i = n - 1; i >= 0; i--) {
while (stack.size() > 1 && A[stack.back()] > A[i]) {
int j = stack.back();
stack.pop_back();
cur -= 1L * -(j - stack.back()) * A[j];
}
cur += 1L * -(i - stack.back()) * A[i];
stack.push_back(i);
res = max(res, left[i] + cur - A[i]);
}
return res;
}
1 : Initialization
long long maximumSumOfHeights(vector<int>& A) {
Defines the function signature, initializing the parameters and starting the function.
2 : Initialization
int n = A.size();
Calculates the size of the array A and stores it in variable n.
3 : Initialization
vector<long long> left(n), stack = {-1};
Initializes a vector `left` to store partial results and a stack with a single element -1.
4 : Variables
long long res = 0, cur = 0;
Declares two variables: `res` to store the final result and `cur` to store intermediate values.
5 : Loop
for (int i = 0; i < n; i++) {
Starts a loop over the array from index 0 to n-1.
6 : Stack Operation
while (stack.size() > 1 && A[stack.back()] > A[i]) {
Checks if the stack contains more than one element and if the current element is smaller than the top element of the stack.
7 : Stack Operation
int j = stack.back();
Stores the index of the top element of the stack in variable `j`.
8 : Stack Operation
stack.pop_back();
Removes the top element from the stack.
9 : Calculation
cur -= 1L * (j - stack.back()) * A[j];
Updates the `cur` variable by subtracting the contribution of the removed element.
10 : Calculation
cur += 1L * (i - stack.back()) * A[i];
Updates the `cur` variable by adding the contribution of the current element.
11 : Stack Operation
stack.push_back(i);
Adds the current index to the stack.
12 : Calculation
left[i] = cur;
Stores the current value of `cur` in the `left` vector at index `i`.
13 : Initialization
stack = {n};
Reinitializes the stack with a single element `n`.
14 : Initialization
cur = 0;
Resets the `cur` variable to 0.
15 : Loop
for (int i = n - 1; i >= 0; i--) {
Starts a second loop over the array from index n-1 to 0.
16 : Stack Operation
while (stack.size() > 1 && A[stack.back()] > A[i]) {
Checks if the stack contains more than one element and if the current element is smaller than the top element of the stack.
17 : Stack Operation
int j = stack.back();
Stores the index of the top element of the stack in variable `j`.
18 : Stack Operation
stack.pop_back();
Removes the top element from the stack.
19 : Calculation
cur -= 1L * -(j - stack.back()) * A[j];
Updates the `cur` variable by subtracting the contribution of the removed element.
20 : Calculation
cur += 1L * -(i - stack.back()) * A[i];
Updates the `cur` variable by adding the contribution of the current element.
21 : Stack Operation
stack.push_back(i);
Adds the current index to the stack.
22 : Calculation
res = max(res, left[i] + cur - A[i]);
Updates the `res` variable with the maximum value between the current `res` and the sum of `left[i]`, `cur`, and `A[i]`.
23 : Return
return res;
Returns the final result stored in `res`.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is linear, O(n), as we process each tower at most twice.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) due to the need for storing intermediate results in arrays.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus