題目來源

力扣每日一題；題序：2865

我的題解

方法一 暴力枚舉

將每個位置都作為山峰來進行遍歷，計算每個山峰下的最大山脈數(shù)組和

時間復(fù)雜度：O($n^2$)
空間復(fù)雜度：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;
}

方法二 單調(diào)棧+前、后綴和

首先需要知道山狀數(shù)組是會從山頂將數(shù)組分為兩個部分，數(shù)組左側(cè)構(gòu)成非遞減，數(shù)組右側(cè)構(gòu)成非遞增。想要使得數(shù)組元素盡可能大，需要使得heights[i]取值為maxHeights[i]，此時假設(shè)區(qū)間[0,i]構(gòu)成的非遞減元素和最大值為prefix[i]，區(qū)間[i,n-1]構(gòu)成的非遞增數(shù)組元素和的最大值為suffix[i]，則這時的山狀數(shù)組的元素之和為：prefix[i]+suffic[i]-maxHeights[i]。減去maxHeights[i]是因為maxHeights[i]在左側(cè)和右側(cè)都被計算進去了，也就是計算了兩次，所以需要減去一次。接下來分別討論左側(cè)和右側(cè)的前綴和以及后綴和的計算：

• 左側(cè)的非遞減（求前綴和）：將maxHeights依次入棧，對于i位置元素來說，不斷從棧頂彈出元素，直到棧中元素是一個非遞減情況（也就是棧頂元素小于maxHeights[i]）。假設(shè)棧頂元素為j位置元素，則對于i位置的最大前綴和：prefix[i]=prefix[j]+(i-j)*maxHeights[i]
• 右側(cè)的非遞增（求后綴和）：將maxHeights依次入棧，對于i位置元素來說，不斷從棧頂彈出元素，直到棧中元素是一個非遞減情況（也就是棧頂元素小于maxHeights[i]）。假設(shè)棧頂元素為j位置元素，則對于i位置的最大前綴和：suffix[i]=suffix[j]+(j-i)*maxHeights[i]

所以最終的山狀數(shù)組的最大值為：max(prefix[i]+suffic[i]-maxHeights[i])

時間復(fù)雜度：O(n)
空間復(fù)雜度：O(n)

有任何問題，歡迎評論區(qū)交流，歡迎評論區(qū)提供其它解題思路（代碼），也可以點個贊支持一下作者哈😄~