链接:2866. 美丽塔 II
关联:
很有质量的一道题目了,难度应该评定低了…2000 分的题目。
承接上题,如果数据量放大后,断然不会用两层循环去解题。实际上选定 i 作为峰值时,后缀 和 前缀 的状态是固定的,我们只需要将 前缀、后缀 这两个数据处理好,是不是就可以直接获取到答案了。
思路:以后缀为例
单调栈的思路比较直接,但是编码过程中维护一些变量啥的、边界情况啥的 就比较难处理,属于十分易错的。
技巧:
推荐阅读:超高质量题解:[Java/Python3/C++]前后缀和+单调栈:以每个最大高度为峰值构造美丽塔【图解】 这个图文结合,再自己手绘一下单调栈的情况就能很快速的理解了~
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;
}
};