美丽塔 II (LeetCode日记)

发布时间：2023年12月22日

LeetCode-2866-美丽塔 II

题目信息:

给你一个长度为 $n$ 下标从 $0$ 开始的整数数组 $ma x He i g h t s$ 。

你的任务是在坐标轴上建 $n$ 座塔。第 $i$ 座塔的下标为 $i$ ，高度为 $h e i g h t s [i]$ 。

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

$1 <= h e i g h t s [i] <= ma x He i g h t s [i]$
heights 是一个山脉数组。

如果存在下标 $i$ 满足以下条件，那么我们称数组 $h e i g h t s$ 是一个山脉数组：

对于所有 $0 < j <= i$ ，都有 $h e i g h t s [j ? 1] <= h e i g h t s [j]$
对于所有 $i <= k < n ? 1$ ，都有 $h e i g h t s [k + 1] <= h e i g h t s [k]$

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

示例1：

输入： $ma x He i g h t s = [5, 3, 4, 1, 1]$
输出：13
解释：和最大的美丽塔方案为 $h e i g h t s = [5, 3, 3, 1, 1]$ ，这是一个美丽塔方案
因为：

$1 <= h e i g h t s [i] <= ma x He i g h t s [i]$
$h e i g h t s$ 是个山脉数组，峰值在 $i = 0$ 处。

则有：13是所有美丽塔方案中的最大高度和。

示例2：

输入： $ma x He i g h t s = [6, 5, 3, 9, 2, 7]$
输出：22
解释：和最大的美丽塔方案为 $h e i g h t s = [3, 3, 3, 9, 2, 2]$ ，这是一个美丽塔方案
因为：

$1 <= h e i g h t s [i] <= ma x He i g h t s [i]$
$h e i g h t s$ 是个山脉数组，峰值在 $i = 3$ 处。

则有：22 是所有美丽塔方案中的最大高度和。

示例3：

输入：$maxHeights = [3,2,5,5,2,3] $
输出：18
解释：和最大的美丽塔方案为 $h e i g h t s = [2, 2, 5, 5, 2, 2]$ ，这是一个美丽塔方案
因为：

$1 <= h e i g h t s [i] <= ma x He i g h t s [i]$
$h e i g h t s$ 是个山脉数组，最大值在 $i = 2$ 处。

注意，在这个方案中，i = 3 也是一个峰值。
18 是所有美丽塔方案中的最大高度和。

提示：

$1 <= n == ma x He i g h t s <= 105$
$1 <= ma x He i g h t s [i] <= 109$

题目类型：栈、数组、单调栈

题解

Leetcode定级为中等难度，标准的做法，对我来说却难的飞起。做题做的太少咯。

下面我们看题目解析。
根据题意可以知道，假设数组的长度为 $n$ ，对于山状数组 $h e i g h t s$
定义如下：

假设 $h e i g h t s [i]$ 为数组中的最大值，则 $i$ 左边的值均小于等于 $h e i g h t s [i]$ ， $i$ 右边的值均小于等于
$h e i g h t s [i]$ ；
$i$ 的左侧，从 $0$ 开始到 $i$ 为非递减关系，即 $j \in [1, i]$ 时，均满足 $h e i g h t s [j ? 1] \leq h e i g h t s [j]$ ;
$i$ 的右侧，从 $i$ 开始到 $n ? 1$ 为非递增关系，即 $j \in [i, n ? 2]$ 时，均满足 $h e i g h t s [j + 1] \leq h e i g h t s [j]$ ;

题目给定了山状数组数组中每个元素的上限，即 $h e i g h t s [i] \leq ma x He i g h t s [i]$ ，题目要求返回的山状数组所有元素之和的最大值。根据以上分析可知：

对于 $j \in [0, i ? 1]$ 时，此时 $ma x ? (h e i g h t s [j]) = min ? (h e i g h t s [j + 1], ma x He i g h t s [j])$
对于 $j \in [i + 1, n ? 1]$ 时，此时 $ma x ? (h e i g h t s [j]) = min ? (h e i g h t s [j ? 1], ma x He i g h t s [j])$
假设此时山状数组的山顶为 $h e i g h t s [i]$ ，此时整个山状数组的所有元素的最大值即可确定，此时数组元素和的最大值也可确定
对于数组中的每个元素尽量取最大值使得整个数组元素之和最大

暴力法：
根据以上分析，我们依次枚举以 $ma x He i g h t s [i]$ 为山顶的山状数组元素之和即可求出最大的高度和。最直接的办法就是两层循环，外层循环依次枚举 $ma x He i g h t s [i]$ 为山顶，在内层循环中分别求出 $i$ 的左侧元素与右侧的元素，即可求出所有元素之和，此时需要的时间复杂度为 $O(n^2)$ 。
请看我的暴力代码：（773 / 785 个通过的测试用例，会超时！！！）

class Solution(object):
    def maximumSumOfHeights(self, maxHeights):
        """
        :type maxHeights: List[int]
        :rtype: int
        """

        lens = len(maxHeights)
        heights = [0] * lens
        maxiume = 0
        for i in range(lens):
            n = i - 1
            heights[i] = maxHeights[i]
            while n >= 0: # 先处理左边递增
                heights[n] = min(heights[n + 1], maxHeights[n])
                n = n-1
            n = i + 1
            while n < lens: # 再处理右边递减
                heights[n] = min(heights[n - 1], maxHeights[n])
                n = n + 1
            maxiume = max(sum(heights), maxiume)
            heights = [0] * lens
        return maxiume

按照题目给定的数量级会存在超时，需要进一步优化。

我只会简单的方法了，现在向大家介绍一下大佬们的想法思路。
动态规划 + 单调栈：
我们定义 $f [i]$ 表示前 $i + 1$ 座塔中，以最后一座塔作为最高塔的美丽塔方案的高度和。我们可以得到如下的状态转移方程：
$f[i]=\left\{\begin{array}{ll}f[i-1]+\text { heights }[i], & \text { if heights }[i] \geq \text { heights }[i-1] \\\text { heights }[i] \times(i-j)+f[j], & \text { if heights }[i]<\text { heights }[i-1]\end{array}\right.$
其中 $j$ 是最后一座塔左边第一个高度小于等于 $h e i g h t s [i]$ 的塔的下标。我们可以使用单调栈来维护这个下标。至于什么是单调栈，不懂得小伙伴可以去其他博客上学习学习，我在这里就不一一赘述了。
我们可以使用类似的方法求出 $g [i]$ ，表示从右往左，以第 iii 座塔作为最高塔的美丽塔方案的高度和。最终答案即为 $f [i] + g [i] ? h e i g h t s [i]$ 的最大值。

Ok,下面请看代码：

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))

研究生在读，我会尽量保持LeetCode每日一题的思路和代码输出。希望大家多多支持。
水平有限，希望各位大佬能够批评指正。您的教诲是我进步的船帆。
希望各位跟我一样的小白能跟我一起参与到做题和讨论中来。共同进步是我所能期盼的最高愿想。
您的点赞和关注是我坚持分享的动力泉源，希望能将这件简单平凡的事一直做下去。感谢大家。

文章来源:https://blog.csdn.net/weixin_52242569/article/details/135128255
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！