网站备案号有效期,网络建站程序,1688货源网下载app,创造与魔法官方网站一起做喜欢的事2024.1.24 题目来源我的题解方法一 暴力枚举方法二 单调栈前、后缀和 题目来源
力扣每日一题#xff1b;题序#xff1a;2865
我的题解
方法一 暴力枚举 将每个位置都作为山峰来进行遍历#xff0c;计算每个山峰下的最大山脉数组和 时间复杂度#xff1a;O( n 2 n^2 n2)… 2024.1.24 题目来源我的题解方法一 暴力枚举方法二 单调栈前、后缀和 题目来源
力扣每日一题题序2865
我的题解
方法一 暴力枚举 将每个位置都作为山峰来进行遍历计算每个山峰下的最大山脉数组和 时间复杂度O( n 2 n^2 n2) 空间复杂度O(1) public long maximumSumOfHeights(ListInteger maxHeights) {int nmaxHeights.size();long res0;for(int i0;in;i){resMath.max(res,getSum(maxHeights,i));}return res;
}
public long getSum(ListInteger maxHeights,int index){long resmaxHeights.get(index);int tmaxHeights.get(index);for(int iindex-1;i0;i--){int curmaxHeights.get(i);if(curt){rescur;tcur;}else{rest;}}tmaxHeights.get(index);for(int iindex1;imaxHeights.size();i){int curmaxHeights.get(i);if(curt){rescur;tcur;}else{rest;}}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) 有任何问题欢迎评论区交流欢迎评论区提供其它解题思路代码也可以点个赞支持一下作者哈~
