[M单调栈] lc2866. 美丽塔 II(单调栈+前后缀分解+经典好题+题单)

本文主要是介绍[M单调栈] lc2866. 美丽塔 II(单调栈+前后缀分解+经典好题+题单)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

- 1. 题目来源
- 2. 题目解析

1. 题目来源

链接：2866. 美丽塔 II

关联：

关联博文：[M枚举] lc2865. 美丽塔 I(枚举+前后缀分解+题单)
超高质量题解：[Java/Python3/C++]前后缀和+单调栈：以每个最大高度为峰值构造美丽塔【图解】

2. 题目解析

很有质量的一道题目了，难度应该评定低了…2000 分的题目。

承接上题，如果数据量放大后，断然不会用两层循环去解题。实际上选定 i 作为峰值时，后缀和前缀的状态是固定的，我们只需要将前缀、后缀这两个数据处理好，是不是就可以直接获取到答案了。

思路：以后缀为例

从后往前遍历数组，维护一个后缀和，该后缀和表示当前元素作为顶峰时，后缀的山脉高度总和。
- 当目前的山脉比前面的高时，后缀和直接累加即可。
- 当目前的山脉比前面的低时，就可以根据单调栈找到次高值将其山脉高度变为降序序列。这个时候，出栈的这部分山脉高度都会比当前山脉高，后缀和需要减去对应的差值。

单调栈的思路比较直接，但是编码过程中维护一些变量啥的、边界情况啥的就比较难处理，属于十分易错的。

技巧：

针对栈中第一次添加元素进来时，右区间还没有对应值，可以先给栈上加入哨兵节点，保证栈不为空，右区间哨兵节点：n，左区间哨兵节点 -1。

推荐阅读：超高质量题解：[Java/Python3/C++]前后缀和+单调栈：以每个最大高度为峰值构造美丽塔【图解】这个图文结合，再自己手绘一下单调栈的情况就能很快速的理解了~

时间复杂度： $O (n)$
空间复杂度： $O (n)$

class Solution {
public:long long maximumSumOfHeights(vector<int>& maxHeights) {int n = maxHeights.size();vector<long long> sufSums(n);   // 后缀和数组stack<int> st;      // 单调栈st.push(n);         // 栈底为n表示后缀和边界long long sufS = 0; // 后缀和for(int i = n - 1; i >= 0; i--){while(st.size() > 1 && maxHeights[i] <= maxHeights[st.top()]){// 在到达栈底n之前，弹出位于当前位置右侧的小于等于当前位置最大高度的索引int t = st.top();   // 获取要弹出的元素st.pop();           // 弹出sufS -= (long long)maxHeights[t] * (st.top() - t);  // 后缀和减去弹出索引对应的区间包含的高度和}sufS += (long long)maxHeights[i] * (st.top() - i);      // 后缀和累加要加入的索引对应的区间包含的高度和sufSums[i] = sufS;      // 记录后缀和st.push(i);             // 元素入栈}while(!st.empty())st.pop(); // 清空栈st.push(-1);                // 栈底为-1表示前缀和边界long long res = 0;  // 结果值long long preS = 0; // 前缀和for(int i = 0; i < n; i++){while(st.size() > 1 && maxHeights[i] <= maxHeights[st.top()]){// 在到达栈底-1之前，弹出位于当前位置左侧的小于等于当前位置最大高度的索引int t = st.top();st.pop();preS -= (long long)maxHeights[t] * (t - st.top());  // 前缀和和减去弹出索引对应的区间包含的高度和}preS += (long long)maxHeights[i] * (i - st.top());      // 前缀和累加要加入的索引对应的区间包含的高度和res = max(res, preS + sufSums[i] - maxHeights[i]);      // 得到当前位置前后缀和，更新最大值st.push(i);     // 元素入栈}return res;        }
};