题目链接

.2866 美丽塔 II : 2072

题目描述

给你一个长度为nnn 下标从000 开始的整数数组 。

你的任务是在坐标轴上建nnn 座塔。第iii 座塔的下标为iii ，高度为[i][i][i] 。

如果以下条件满足，我们称这些塔是 美丽 的：

如果存在下标iii 满足以下条件，那么我们称数组s 是一个 山状 数组：

请你返回满足 美丽塔 要求的方案中，高度和的最大值 。

示例 1：

输入： = [5,3,4,1,1]

输出：13

解释：和最大的美丽塔方案为 = [5,3,3,1,1] ，这是一个美丽塔方案，因为：

示例 2：

输入： = [6,5,3,9,2,7]

输出：22

解释： 和最大的美丽塔方案为 = [3,3,3,9,2,2] ，这是一个美丽塔方案，因为：

示例 3：

输入： = [3,2,5,5,2,3]

输出：18

解释：和最大的美丽塔方案为 = [2,2,5,5,2,2] ，这是一个美丽塔方案，因为：

提示： 解法：单调栈 + 前后缀分解

我们定义 和：

为了便于我们操作，我们将 和 都偏移一个长度，即 和 的长度都为n+1n + 1n+1。

举例 ：

对于=[5,3,4,1,1] = [5,3,4,1,1]=[5,3,4,1,1]，则它的 和 分别为：

那么最大的美丽塔高度和为max{pre[i]+suf[i]}(0≤i≤n)max\{ pre[i] + suf[i]\} \quad (0 \leq i \leq n)max{pre[i]+suf[i]}(0≤i≤n)

现在问题的关键在于如何求出 和。

我们可以使用单调栈。

对于 ，我们使用一个栈，从小到大的记录元素下标 (从栈底到栈顶)。假设当前遍历到的元素为[i][i][i]，并且栈顶元素 大于等于 当前元素，即[()]≥[i][()] \geq [i][()]≥[i]，那么我们就要不断地弹出栈顶元素。

上述操作完成之后，要么栈顶元素小于当前元素，即[()]要么此时栈为空。

我们就设jjj 为当前的栈顶元素，即j=()j = ()j=()；如果栈为空，就设置j=−1j = -1j=−1。

那么此时(j,i](j,i](j,i] 这一区间的值都应该是[i][i][i]，总和就是sum=(i−j)×[i]sum = (i - j) \times [i]sum=(i−j)×[i]。

所以此时pre[i]=sum+pre[j]pre[i] = sum + pre[j]pre[i]=sum+pre[j]。

对于求 也是同理。

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

C++代码：

using LL = long long;
class Solution {
public:
    long long maximumSumOfHeights(vector& nums) {
        int n = nums.size();
        vector pre(n + 1) , suf(n + 1);
        stack stk{{-1}};
        for(int i = 0;i < n;i++){
            while(stk.size() > 1 && nums[stk.top()] >= nums[i]){
                stk.pop();
            }
            int j = stk.top();
            pre[i + 1] += (i - j) * 1LL * nums[i];
            pre[i + 1] += pre[j + 1];
            stk.push(i);
        }
        //清空栈
        while(!stk.empty()) stk.pop();
        stk.push(n);
        for(int i = n - 1;i >= 0;i--){
            while(stk.size() > 1 && nums[stk.top()] >= nums[i]){
                stk.pop();
            }
            int j = stk.top();
            suf[i] += (j - i) * 1LL * nums[i];
            suf[i] += suf[j];
            stk.push(i); 
        }
        LL ans = 0;
        for(int i = 0;i <= n;i++){
            ans = max(pre[i] + suf[i] , ans);
        }
        return ans;
    }
};