1499.满足不等式的最大值

链接：1499.满足不等式的最大值
难度：Hard
标签：队列、数组、滑动窗口、单调队列、堆（优先队列）
简介：定一个长度为 n 的环形整数数组 nums ，返回 nums 的非空 子数组 的最大可能和 。

题解 1 - cpp

• 编辑时间：2023-07-23
• 执行用时：16ms
• 内存消耗：19.6MB
• 编程语言：cpp
• 解法介绍：统计左右最大高度。

class Solution {
public:
    int trap(vector<int>& height) {
        int sum = 0, n = height.size();
        vector<int> r(n, 0);
        for (int i = n - 1, cur = 0; i >= 0; i--) {
            r[i] = cur;
            cur = max(cur, height[i]);
        }
        for (int i = 0, cur = 0; i < n; i++) {
            cur = max(cur, height[i]);
            sum += max(0, min(cur, r[i]) - height[i]);
        }
        return sum;
    }
};

题解 2 - python

• 编辑时间：2023-07-23
• 执行用时：68ms
• 内存消耗：17.7MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def trap(self, height: List[int]) -> int:
        sum = 0
        n = len(height)
        cur = 0
        r = [0] * n
        for i in range(n-1, -1, -1):
            r[i] = cur
            cur = max(cur, height[i])
        cur = 0
        for i in range(n):
            cur = max(cur, height[i])
            sum += max(0, min(cur, r[i])-height[i])
        return sum

题解 3 - rust

• 编辑时间：2023-07-23
• 内存消耗：2.2MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn trap(height: Vec<i32>) -> i32 {
        let mut sum = 0;
        let n = height.len();
        let mut cur = 0;
        let mut r = vec![0; n];
        for i in (0..n).rev() {
            r[i] = cur;
            cur = cur.max(height[i]);
        }
        cur = 0;
        for i in 0..n {
            cur = cur.max(height[i]);
            sum += 0.max(cur.min(r[i]) - height[i]);
        }
        sum
    }
}