leetcode(力扣) 2866. 美丽塔 II

这篇具有很好参考价值的文章主要介绍了leetcode(力扣) 2866. 美丽塔 II。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

原题链接

暴力做法 (时间复杂度 O(n^2))

每次选取下标 i 为峰值, 进行 n 次,对每次取max就可以找到答案


对于 i 左边的序列: 需要满足序列是非递减的, 同时每个值尽可能大

所以满足: j 的位置上的数 <= (j, i] 上的最小的值 (等于时取得最大值) , 同时需要保证 j 位置上的数要小于heights[j] (题目中的要求,美丽塔的要求); 即 t = min(pre, heights[j]) pre表示的是 下标是 (j, i] 的最小的值


对于 i 右边的序列: 需要满足序列是非递增的,同时每个值尽可能大

所以满足:j 的位置上的数 <= [i, j) 上的最小的值 (等于时取得最大值), 同时需要保证 j 位置上的数要小于heights[j]; 即 t = min(pre, heights[j]) pre表示的是 下标是 [i, j) 的最小的值

class Solution {
public:
    long long maximumSumOfHeights(vector<int>& heights) {
        int n = heights.size();
        long long res = 0;
        for (int i = 0; i < n; i ++ )
        {
            int pre = heights[i];
            long long sum = heights[i] * 1LL;
            for (int j = i - 1; j >= 0; j --)  // pre表示的是下标 (j, i] 中heights中的最小值
            {    
                sum += min(pre, heights[j]);    // 下标从i - 1开始, 每次取min,可以保证当下标为 j 时 pre 表示的就是 [j + 1, i] 的最小值
                pre = min(pre, heights[j]);    
            }
            pre = heights[i];
            for (int j = i + 1; j < n; j ++)  // pre表示的是下标 [i, j) 中heights中的最小值
            {
                sum += min(pre, heights[j]);
                pre = min(pre, heights[j]);
            }
            res = max(sum, res);
        }
        return res;
    }
};

单调栈做法 (时间复杂度 O(n)) (tag: 单调栈、 动态规划)

st1 和 st2 存的都是下标

下面图片模拟的是 第一个 for循环, 标红的是 进入 if(st1.empty()) 这个分支的
p1[4] 为什么加的是 2 x heights[4]呢, 因为此时st1中还有 元素1的下标2, 此时 下标3 和 下标4 的高度应该都为heights[4]
leetcode(力扣) 2866. 美丽塔 II

class Solution {
public:
    long long maximumSumOfHeights(vector<int>& heights) {
        int n = heights.size();
        
        long long res = 0;
        stack<int> st1; stack<int> st2;  // 栈里面存的是 下标
        vector<long long> p1(n); vector<long long> p2(n);    
        // p1 的状态表示是 下标为 i 的 左侧美丽塔高度之和 (包含i本身,同时满足p1[i]是美丽塔高度和的最大值)
        // p2 的状态表示是 下标为 i 的 右侧美丽塔高度之和 (包含i本身,同时满足p1[i]是美丽塔高度和的最大值)

        for (int i = 0; i < n; i ++)
        {
            while (!st1.empty() && heights[i] < heights[st1.top()]) st1.pop(); // 让栈满足 (栈为空 || 栈中元素对应的heights的值是非递减的)
            
           // 栈为空 说明 : i = 0或者 i 前面的山脉高度都比 heights[i] 大, 为了保证序列非递减, 前面的所有数都应该是 heights[i]
            if (st1.empty()) p1[i] = (long long)(i + 1) * heights[i]; 
            else p1[i] = p1[st1.top()]  + (long long)(i - st1.top()) * heights[i] ;
          // 不为空 说明 下标为 (st1.top(), i] 山脉高度 都比 heights[i] 大, 为了保证序列非递减,  (st1.top(), i] 之间的山脉高度都应该是  heights[i]

            st1.emplace(i);
        }

        for (int i = n - 1; i >= 0; i --)  // 需要保证从后往前是一个非递减序列
        {
            while (!st2.empty() && heights[i] < heights[st2.top()]) st2.pop(); 

            if (st2.empty()) p2[i] = (long long)(n - i) * heights[i] * 1LL;
            else p2[i] = p2[st2.top()] + (long long)(st2.top() - i) * heights[i] ;
            st2.emplace(i);

            res = max(res, p1[i] + p2[i] - heights[i]);  // 看p1和p2的状态表示,都包含的 i,要减去重复的一个
        }
        return res;
    }
};

觉得写的不错的话,点个赞吧!~文章来源地址https://www.toymoban.com/news/detail-861466.html

到了这里,关于leetcode(力扣) 2866. 美丽塔 II的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • leetcode原题:绘制直线(位运算)

    题目: 已知一个由像素点组成的单色屏幕,每行均有 w 个像素点,所有像素点初始为 0 ,左上角位置为 (0,0) 。 现将每行的像素点按照「每 32 个像素点」为一组存放在一个 int 中,再依次存入长度为 length 的一维数组中。 我们将在屏幕上绘制一条从点 (x1,y) 到点 (x2,y) 的直线(

    2024年02月12日
    浏览(12)
  • leetcode原题: 堆箱子(动态规划实现)

    题目: 给你一堆n个箱子,箱子宽 wi、深 di、高 hi。箱子不能翻转,将箱子堆起来时,下面箱子的宽度、高度和深度必须大于上面的箱子。实现一种方法,搭出最高的一堆箱子。箱堆的高度为每个箱子高度的总和。 输入使用数组 [wi, di, hi] 表示每个箱子。 示例:  输入:box

    2024年02月11日
    浏览(13)
  • leetcode原题:颜色填充(经典的递归问题)

    题目: 编写函数,实现许多图片编辑软件都支持的「颜色填充」功能。 待填充的图像用二维数组 image 表示,元素为初始颜色值。初始坐标点的行坐标为 sr 列坐标为 sc。需要填充的新颜色为 newColor 。 「周围区域」是指颜色相同且在上、下、左、右四个方向上存在相连情况的

    2024年02月12日
    浏览(15)
  • 【Leetcode】2865. 美丽塔 I

    题目链接 给你一个长度为 n 下标从 0 开始的整数数组 maxHeights 。 你的任务是在坐标轴上建 n 座塔。第 i 座塔的下标为 i ,高度为 heights[i] 。 如果以下条件满足,我们称这些塔是 美丽 的: 1 = heights[i] = maxHeights[i] heights 是一个 山脉 数组。 如果存在下标 i 满足以下条件,那么

    2024年02月22日
    浏览(14)
  • ​LeetCode解法汇总2865. 美丽塔 I

    https://github.com/September26/java-algorithms 给你一个长度为  n  下标从  0  开始的整数数组  maxHeights  。 你的任务是在坐标轴上建  n  座塔。第  i  座塔的下标为  i  ,高度为  heights[i]  。 如果以下条件满足,我们称这些塔是  美丽  的: 1 = heights[i] = maxHeights[i] heights  是一

    2024年01月25日
    浏览(17)
  • 【LeetCode每日一题】2865. 美丽塔 I

    2024-1-24 2865. 美丽塔 I 初始化变量 ans 为0,用于记录最大的和值。 获取整数列表的长度,保存到变量 n 中。 使用一个循环遍历列表中的每个位置,从0到 n-1 。 在循环中,首先获取当前位置的高度 y ,并将其赋值给变量 t ,用于记录当前位置的和值。 使用一个内层循环,从当

    2024年01月25日
    浏览(14)
  • 关于岛屿的三道leetcode原题:岛屿周长、岛屿数量、统计子岛屿

    题1: 岛屿周长 给定一个 row x col 的二维网格地图 grid ,其中:gridi = 1 表示陆地, gridi = 0 表示水域。 网格中的格子 水平和垂直 方向相连(对角线方向不相连)。整个网格被水完全包围,但其中恰好有一个岛屿(或者说,一个或多个表示陆地的格子相连组成的岛屿)。 岛屿

    2024年02月10日
    浏览(25)
  • LeetCode 2865. 美丽塔 I,前后缀分离+单调栈

    1、题目描述 给你一个长度为  n  下标从  0  开始的整数数组  maxHeights  。 你的任务是在坐标轴上建  n  座塔。第  i  座塔的下标为  i  ,高度为  heights[i]  。 如果以下条件满足,我们称这些塔是  美丽  的: 1 = heights[i] = maxHeights[i] heights  是一个  山脉  数组。 如果

    2024年01月25日
    浏览(14)
  • leetcode原题 一次编辑(判定字符串是否只需要一次(或者零次)编辑)

    题目: 字符串有三种编辑操作:插入一个英文字符、删除一个英文字符或者替换一个英文字符。 给定两个字符串,编写一个函数判定它们是否只需要一次(或者零次)编辑。 输入:  first = \\\"pale\\\" second = \\\"ple\\\" 输出: True 解题思路: 本题可以分为以下几种情况来处理: 1. 两个字符串长

    2024年02月13日
    浏览(12)
  • 最大正方形(力扣)暴力 + 动态规划 JAVA

    在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵内,找到只包含 ‘1’ 的最大正方形,并返回其面积。 示例 1: 输入:matrix = [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,“1”,“1”],[“1”,“0”,“0”,“1”,“0”]] 输出:4 示例 2: 输入:m

    2024年02月15日
    浏览(29)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包