首页 > 其他分享 >leetcode(力扣) 2866. 美丽塔 II

leetcode(力扣) 2866. 美丽塔 II

时间:2024-04-28 22:55:05浏览次数:24  
标签:pre II p1 下标 long heights 力扣 st1 leetcode

原题链接

暴力做法 (时间复杂度 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]

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]);
        }
        return res;
    }
};

觉得写的不错的话,点个赞吧!~

标签:pre,II,p1,下标,long,heights,力扣,st1,leetcode
From: https://www.cnblogs.com/xxctx/p/18164530

相关文章

  • SystemVerilog -- 6.4 Interface ~ Clocking Block Part II
    SystemVerilogClockingBlockPartII时钟模块允许在指定的时钟事件对输入进行采样并驱动输出。如果提到时钟模块的输入skew,则该模块中的所有输入信号都将在时钟事件之前以skew时间单位进行采样。如果提到时钟模块的输出skew,则该模块中的输出信号都将在相应的时钟事件之后以ske......
  • 力扣-231. 2 的幂
    1.题目题目地址(231.2的幂-力扣(LeetCode))https://leetcode.cn/problems/power-of-two/?envType=study-plan-v2&envId=primers-list题目描述给你一个整数n,请你判断该整数是否是2的幂次方。如果是,返回true;否则,返回false。如果存在一个整数x使得 n==2x,则认为......
  • 力扣-709. 转换成小写字母
    1.题目题目地址(-力扣(LeetCode))https://leetcode.cn/problems/to-lower-case/?envType=study-plan-v2&envId=primers-list题目描述给你一个字符串s,将该字符串中的大写字母转换成相同的小写字母,返回新的字符串。 示例1:输入:s="Hello"输出:"hello"示例2:输入:s="......
  • 力扣-1979. 找出数组的最大公约数
    1.题目介绍题目地址(c-力扣(LeetCode))https://leetcode.cn/problems/find-greatest-common-divisor-of-array/题目描述给你一个整数数组nums,返回数组中最大数和最小数的最大公约数。两个数的 最大公约数是能够被两个数整除的最大正整数。 示例1:输入:nums=[2,5,6......
  • Intel Pentium III CPU(Coppermine, Tualatin) L2 Cache Latency, Hardware Prefetch
    这几天,偶然的机会想到了困扰自己和其他网友多年的IntelPentiumIII系列处理器缓存延迟(L2CacheLatency),以及图拉丁核心版本是否支持硬件预取(HardwarePrefetch)问题。手头的支持图拉丁核心处理器的i815主板还在正常服役中,铜矿和图拉丁核心处理器也都有,所以就专门做了这一期调查,感......
  • 力扣-566. 重塑矩阵
    1.题目题目地址(566.重塑矩阵-力扣(LeetCode))https://leetcode.cn/problems/reshape-the-matrix/题目描述在MATLAB中,有一个非常有用的函数reshape,它可以将一个 mxn矩阵重塑为另一个大小不同(rxc)的新矩阵,但保留其原始数据。给你一个由二维数组mat表示的 mxn......
  • 力扣-125. 验证回文串
    1.题目题目地址(125.验证回文串-力扣(LeetCode))https://leetcode.cn/problems/valid-palindrome/题目描述如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后,短语正着读和反着读都一样。则可以认为该短语是一个回文串。字母和数字都属于字母数字字符。......
  • 力扣练习-动态规划
    线性DP3122.使矩阵满足条件的最少操作次数classSolution{/*问题分类:线性DP问题1.每一列元素值相同,相邻列元素值不同,考虑按照列进行状态枚举枚举2.0<=grid[i][j]<=9,值的范围很小只有10个3.f[i][j]可以为考虑前i列并且第i列元素为......
  • 力扣-498. 对角线遍历
    1.题目题目地址(498.对角线遍历-力扣(LeetCode))https://leetcode.cn/problems/diagonal-traverse/题目描述给你一个大小为mxn的矩阵mat,请以对角线遍历的顺序,用一个数组返回这个矩阵中的所有元素。 示例1:输入:mat=[[1,2,3],[4,5,6],[7,8,9]]输出:[1,2,4,7,5,3,6......
  • 力扣-520. 检测大写字母
    1.题目题目地址(520.检测大写字母-力扣(LeetCode))https://leetcode.cn/problems/detect-capital/题目描述我们定义,在以下情况时,单词的大写用法是正确的:全部字母都是大写,比如"USA"。单词中所有字母都不是大写,比如"leetcode"。如果单词不只含有一个字母,只有首字母大写......