2024.1.24力扣每日一题——美丽塔I

发布时间:2024年01月24日

题目来源

力扣每日一题;题序:2865

我的题解

方法一 暴力枚举

将每个位置都作为山峰来进行遍历,计算每个山峰下的最大山脉数组和

时间复杂度:O( n 2 n^2 n2)
空间复杂度:O(1)

public long maximumSumOfHeights(List<Integer> maxHeights) {
 int n=maxHeights.size();
 long res=0;
 for(int i=0;i<n;i++){
     res=Math.max(res,getSum(maxHeights,i));
 }
 return res;
}
public long getSum(List<Integer> maxHeights,int index){
 long res=maxHeights.get(index);
 int t=maxHeights.get(index);
 for(int i=index-1;i>=0;i--){
     int cur=maxHeights.get(i);
     if(cur<=t){
         res+=cur;
         t=cur;
     }else{
         res+=t;
     }
 }
 t=maxHeights.get(index);
 for(int i=index+1;i<maxHeights.size();i++){
     int cur=maxHeights.get(i);
     if(cur<=t){
         res+=cur;
         t=cur;
     }else{
         res+=t;
     }
 }
 return res;
}
方法二 单调栈+前、后缀和

首先需要知道山状数组是会从山顶将数组分为两个部分,数组左侧构成非递减,数组右侧构成非递增。想要使得数组元素尽可能大,需要使得heights[i]取值为maxHeights[i],此时假设区间[0,i]构成的非递减元素和最大值为prefix[i],区间[i,n-1]构成的非递增数组元素和的最大值为suffix[i],则这时的山状数组的元素之和为:prefix[i]+suffic[i]-maxHeights[i]。减去maxHeights[i]是因为maxHeights[i]在左侧和右侧都被计算进去了,也就是计算了两次,所以需要减去一次。接下来分别讨论左侧和右侧的前缀和以及后缀和的计算:

  • 左侧的非递减(求前缀和):将maxHeights依次入栈,对于i位置元素来说,不断从栈顶弹出元素,直到栈中元素是一个非递减情况(也就是栈顶元素小于maxHeights[i])。假设栈顶元素为j位置元素,则对于i位置的最大前缀和:prefix[i]=prefix[j]+(i-j)*maxHeights[i]
  • 右侧的非递增(求后缀和):将maxHeights依次入栈,对于i位置元素来说,不断从栈顶弹出元素,直到栈中元素是一个非递减情况(也就是栈顶元素小于maxHeights[i])。假设栈顶元素为j位置元素,则对于i位置的最大前缀和:suffix[i]=suffix[j]+(j-i)*maxHeights[i]

所以最终的山状数组的最大值为:max(prefix[i]+suffic[i]-maxHeights[i])

时间复杂度:O(n)
空间复杂度:O(n)


有任何问题,欢迎评论区交流,欢迎评论区提供其它解题思路(代码),也可以点个赞支持一下作者哈😄~

文章来源:https://blog.csdn.net/weixin_42075274/article/details/135831770
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。