美丽塔 II (LeetCode日记)

2023-12-22 09:30:56

LeetCode-2866-美丽塔 II

题目信息:

给你一个长度为 n n n 下标从 0 0 0 开始的整数数组 m a x H e i g h t s maxHeights maxHeights

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

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

  1. 1 < = h e i g h t s [ i ] < = m a x H e i g h t s [ i ] 1 <= heights[i] <= maxHeights[i] 1<=heights[i]<=maxHeights[i]
  2. heights 是一个 山脉 数组。

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

  • 对于所有 0 < j < = i 0 < j <= i 0<j<=i ,都有 h e i g h t s [ j ? 1 ] < = h e i g h t s [ j ] heights[j - 1] <= heights[j] heights[j?1]<=heights[j]
  • 对于所有 i < = k < n ? 1 i <= k < n - 1 i<=k<n?1 ,都有 h e i g h t s [ k + 1 ] < = h e i g h t s [ k ] heights[k + 1] <= heights[k] heights[k+1]<=heights[k]

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

  • 示例1:

输入: m a x H e i g h t s = [ 5 , 3 , 4 , 1 , 1 ] maxHeights = [5,3,4,1,1] maxHeights=[5,3,4,1,1]
输出:13
解释:和最大的美丽塔方案为 h e i g h t s = [ 5 , 3 , 3 , 1 , 1 ] heights = [5,3,3,1,1] heights=[5,3,3,1,1] ,这是一个美丽塔方案
因为:

  • 1 < = h e i g h t s [ i ] < = m a x H e i g h t s [ i ] 1 <=heights[i] <= maxHeights[i] 1<=heights[i]<=maxHeights[i]
  • h e i g h t s heights heights 是个山脉数组,峰值在 i = 0 i = 0 i=0 处 。

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

  • 示例2:

输入: m a x H e i g h t s = [ 6 , 5 , 3 , 9 , 2 , 7 ] maxHeights = [6,5,3,9,2,7] maxHeights=[6,5,3,9,2,7]
输出:22
解释: 和最大的美丽塔方案为 h e i g h t s = [ 3 , 3 , 3 , 9 , 2 , 2 ] heights =[3,3,3,9,2,2] heights=[3,3,3,9,2,2] ,这是一个美丽塔方案
因为:

  • 1 < = h e i g h t s [ i ] < = m a x H e i g h t s [ i ] 1 <= heights[i] <= maxHeights[i] 1<=heights[i]<=maxHeights[i]
  • h e i g h t s heights heights 是个山脉数组,峰值在 i = 3 i = 3 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 ] heights =[2,2,5,5,2,2] heights=[2,2,5,5,2,2] ,这是一个美丽塔方案
因为:

  • 1 < = h e i g h t s [ i ] < = m a x H e i g h t s [ i ] 1 <= heights[i] <= maxHeights[i] 1<=heights[i]<=maxHeights[i]
  • h e i g h t s heights heights 是个山脉数组,最大值在 i = 2 i = 2 i=2 处。

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

提示:

  • 1 < = n = = m a x H e i g h t s < = 105 1 <= n == maxHeights <= 105 1<=n==maxHeights<=105
  • 1 < = m a x H e i g h t s [ i ] < = 109 1 <= maxHeights[i] <= 109 1<=maxHeights[i]<=109

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

题解

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

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

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

题目给定了山状数组数组中每个元素的上限,即 h e i g h t s [ i ] ≤ m a x H e i g h t s [ i ] heights[i]≤maxHeights[i] heights[i]maxHeights[i],题目要求返回的山状数组所有元素之和的最大值。根据以上分析可知:

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

暴力法:
根据以上分析,我们依次枚举以 m a x H e i g h t s [ i ] maxHeights[i] maxHeights[i] 为山顶的山状数组元素之和即可求出最大的高度和。最直接的办法就是两层循环,外层循环依次枚举 m a x H e i g h t s [ i ] maxHeights[i] maxHeights[i]为山顶,在内层循环中分别求出 i i i 的左侧元素与右侧的元素,即可求出所有元素之和,此时需要的时间复杂度为 O ( n 2 ) O(n^2) O(n2)
请看我的暴力代码:(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 ] f[i] f[i] 表示前 i + 1 i+1 i+1 座塔中,以最后一座塔作为最高塔的美丽塔方案的高度和。我们可以得到如下的状态转移方程:
f [ i ] = { f [ i ? 1 ] + ?heights? [ i ] , ?if?heights? [ i ] ≥ ?heights? [ i ? 1 ] ?heights? [ i ] × ( i ? j ) + f [ j ] , ?if?heights? [ i ] < ?heights? [ 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. f[i]={f[i?1]+?heights?[i],?heights?[i]×(i?j)+f[j],??if?heights?[i]?heights?[i?1]?if?heights?[i]<?heights?[i?1]?
其中 j j j 是最后一座塔左边第一个高度小于等于 h e i g h t s [ i ] heights[i] heights[i]的塔的下标。我们可以使用单调栈来维护这个下标。至于什么是单调栈,不懂得小伙伴可以去其他博客上学习学习,我在这里就不一一赘述了。
我们可以使用类似的方法求出 g [ i ] g[i] g[i],表示从右往左,以第 iii 座塔作为最高塔的美丽塔方案的高度和。最终答案即为 f [ i ] + g [ i ] ? h e i g h t s [ i ] f[i]+g[i]?heights[i] f[i]+g[i]?heights[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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。