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

发布时间:2024年01月24日

1. 题目来源

链接:2866. 美丽塔 II

关联:

2. 题目解析

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

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

思路:以后缀为例

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

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


技巧:

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

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


  • 时间复杂度 O ( n ) O(n) O(n)
  • 空间复杂度 O ( n ) 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;        
    }
};
文章来源:https://blog.csdn.net/yl_puyu/article/details/135822367
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。