Medium

题目描述

给你一个长度为 n 的整数数组 heights，表示 n 座连续塔的砖块数量。你的任务是移除一些砖块来形成山形塔排列。在这种排列中，塔的高度先非递减，达到一个或多个连续塔的最大峰值，然后非递增。

返回山形塔排列的最大可能高度总和。

示例 1：

输入：heights = [5,3,4,1,1]
输出：13
解释：我们移除一些砖块使得 heights = [5,3,3,1,1]，峰值在索引 0 处。

示例 2：

输入：heights = [6,5,3,9,2,7]
输出：22
解释：我们移除一些砖块使得 heights = [3,3,3,9,2,2]，峰值在索引 3 处。

示例 3：

输入：heights = [3,2,5,5,2,3]
输出：18
解释：我们移除一些砖块使得 heights = [2,2,5,5,2,2]，峰值在索引 2 或 3 处。

约束条件：

  • 1 <= n == heights.length <= 10³
  • 1 <= heights[i] <= 10⁹

解题思路

这是一道关于山形数组的问题，需要找到最大可能的山形塔高度总和。

核心思路：

  1. 枚举每个位置作为峰值点
  2. 对于每个峰值点，分别向左和向右构建山形结构
  3. 向左时，每个位置的高度不能超过右边位置的高度（非递增）
  4. 向右时，每个位置的高度不能超过左边位置的高度（非递减）

算法步骤：

  1. 遍历数组的每个位置 i 作为峰值
  2. 从峰值向左扫描：每个位置的高度 = min(原高度, 右边位置的最终高度)
  3. 从峰值向右扫描：每个位置的高度 = min(原高度, 左边位置的最终高度)
  4. 计算当前峰值下的总高度，更新最大值

这种方法确保了山形结构的正确性：峰值左侧非递增，右侧非递减。

时间复杂度： O(n²) - 对每个峰值位置都需要扫描整个数组 空间复杂度： O(n) - 需要额外数组存储调整后的高度

虽然存在 O(n) 的单调栈优化解法，但对于此题的数据规模（n ≤ 1000），暴力解法已经足够高效。

代码实现

class Solution {
public:
    long long maximumSumOfHeights(vector<int>& heights) {
        int n = heights.size();
        long long maxSum = 0;
        
        for (int peak = 0; peak < n; peak++) {
            vector<long long> adjusted(n);
            adjusted[peak] = heights[peak];
            
            // 向左填充（非递增）
            for (int i = peak - 1; i >= 0; i--) {
                adjusted[i] = min((long long)heights[i], adjusted[i + 1]);
            }
            
            // 向右填充（非递减）
            for (int i = peak + 1; i < n; i++) {
                adjusted[i] = min((long long)heights[i], adjusted[i - 1]);
            }
            
            // 计算总和
            long long currentSum = 0;
            for (int i = 0; i < n; i++) {
                currentSum += adjusted[i];
            }
            
            maxSum = max(maxSum, currentSum);
        }
        
        return maxSum;
    }
};

class Solution:
    def maximumSumOfHeights(self, heights: List[int]) -> int:
        n = len(heights)
        max_sum = 0
        
        for peak in range(n):
            adjusted = [0] * n
            adjusted[peak] = heights[peak]
            
            # 向左填充（非递增）
            for i in range(peak - 1, -1, -1):
                adjusted[i] = min(heights[i], adjusted[i + 1])
            
            # 向右填充（非递减）
            for i in range(peak + 1, n):
                adjusted[i] = min(heights[i], adjusted[i - 1])
            
            # 计算总和
            current_sum = sum(adjusted)
            max_sum = max(max_sum, current_sum)
        
        return max_sum

public class Solution {
    public long MaximumSumOfHeights(int[] heights) {
        int n = heights.Length;
        long maxSum = 0;
        
        for (int peak = 0; peak < n; peak++) {
            long[] adjusted = new long[n];
            adjusted[peak] = heights[peak];
            
            // 向左填充（非递增）
            for (int i = peak - 1; i >= 0; i--) {
                adjusted[i] = Math.Min(heights[i], adjusted[i + 1]);
            }
            
            // 向右填充（非递减）
            for (int i = peak + 1; i < n; i++) {
                adjusted[i] = Math.Min(heights[i], adjusted[i - 1]);
            }
            
            // 计算总和
            long currentSum = 0;
            for (int i = 0; i < n; i++) {
                currentSum += adjusted[i];
            }
            
            maxSum = Math.Max(maxSum, currentSum);
        }
        
        return maxSum;
    }
}

/**
 * @param {number[]} heights
 * @return {number}
 */
var maximumSumOfHeights = function(heights) {
    const n = heights.length;
    let maxSum = 0;
    
    for (let peak = 0; peak < n; peak++) {
        const adjusted = new Array(n);
        adjusted[peak] = heights[peak];
        
        // 向左填充（非递增）
        for (let i = peak - 1; i >= 0; i--) {
            adjusted[i] = Math.min(heights[i], adjusted[i + 1]);
        }
        
        // 向右填充（非递减）
        for (let i = peak + 1; i < n; i++) {
            adjusted[i] = Math.min(heights[i], adjusted[i - 1]);
        }
        
        // 计算总和
        let currentSum = 0;
        for (let i = 0; i < n; i++) {
            currentSum += adjusted[i];
        }
        
        maxSum = Math.max(maxSum, currentSum);
    }
    
    return maxSum;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小说明
时间复杂度O(n²)枚举 n 个峰值位置，每次需要 O(n) 时间构建山形数组
空间复杂度O(n)需要额外数组存储调整后的高度值

相关题目