2865. 美丽塔 I

单调栈【力扣周赛 364】_哔哩哔哩_bilibili

给你一个长度为 n 下标从 0 开始的整数数组 maxHeights 。

你的任务是在坐标轴上建 n 座塔。第 i 座塔的下标为 i ，高度为 heights[i] 。

如果以下条件满足，我们称这些塔是 美丽 的：

1. 1 <= heights[i] <= maxHeights[i]
2. heights 是一个 山脉 数组。

如果存在下标 i 满足以下条件，那么我们称数组 heights 是一个 山脉 数组：

• 对于所有 0 < j <= i ，都有 heights[j - 1] <= heights[j]
• 对于所有 i <= k < n - 1 ，都有 heights[k + 1] <= heights[k]

请你返回满足 美丽塔 要求的方案中，高度和的最大值 。

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

---

对于没有思路的，至少把暴力的写法搞出来，而不是什么都没有

impl Solution {  
    pub fn maximum_sum_of_heights(max_heights: Vec<i32>) -> i64 {  
        let n = max_heights.len();  
        let mut res = 0i64;  
  
        for i in 0..n {  
            let mut ans = 0i64;  
            let mut cur = max_heights[i] as i64;  
  
            for j in (0..=i).rev() {  
                cur = cur.min(max_heights[j] as i64);  
                ans += cur;  
            }  
  
            cur = max_heights[i] as i64;  
  
            for j in i + 1..n {  
                cur = cur.min(max_heights[j] as i64);  
                ans += cur;  
            }  
  
            res = res.max(ans);  
        }  
  
        res  
    }  
}  
  
#[test]  
pub fn test_it() {  
    Solution::maximum_sum_of_heights(vec![1000000000, 1000000000, 1000000000]);  
}

注意不要缩小返回的值的最小范围为 i64

#算法/brute_force