leetcode2865

题目

Leetcode 2865

美丽塔 I

给你一个长度为 `n` 下标从 **0** 开始的整数数组 `maxHeights` 。

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

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

1 <= heights[i] <= maxHeights[i]
heights 是一个山脉数组。

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

对于所有 0 < j <= i ，都有 heights[j - 1] <= heights[j]
对于所有 i <= k < n - 1 ，都有 heights[k + 1] <= heights[k]

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

示例 1：

输入：maxHeights = [5,3,4,1,1]
输出：13
解释：和最大的美丽塔方案为 heights = [5,3,3,1,1] ，这是一个美丽塔方案，因为：
- 1 <= heights[i] <= maxHeights[i]  
- heights 是个山脉数组，峰值在 i = 0 处。
13 是所有美丽塔方案中的最大高度和。

示例 2：

输入：maxHeights = [6,5,3,9,2,7]
输出：22
解释： 和最大的美丽塔方案为 heights = [3,3,3,9,2,2] ，这是一个美丽塔方案，因为：
- 1 <= heights[i] <= maxHeights[i]
- heights 是个山脉数组，峰值在 i = 3 处。
22 是所有美丽塔方案中的最大高度和。

示例 3：

输入：maxHeights = [3,2,5,5,2,3]
输出：18
解释：和最大的美丽塔方案为 heights = [2,2,5,5,2,2] ，这是一个美丽塔方案，因为：
- 1 <= heights[i] <= maxHeights[i]
- heights 是个山脉数组，最大值在 i = 2 处。
注意，在这个方案中，i = 3 也是一个峰值。
18 是所有美丽塔方案中的最大高度和。

提示：

1 <= n == maxHeights <= 103
1 <= maxHeights[i] <= 109

这道题应该在集训的时候见过，依稀记得用单调栈应该能做到);奈何学的不扎实怎么想都降不下来，只能先交个暴力枚举的方法，在这里认认真真做个笔记；

看完题解后发现和想象中不一样在于：

他所维护的单调栈至始至终只有1(2)个，我却误认为对于每个下标都得开一个栈才能找到非增序列元素和最大值，事实上其中暗含递推关系，使得可以继承停止弹栈时候的状态；

注意观察，山脉数组由左侧的非递减序列和右侧的非递增序列组成；

对于每个下标i,设山脉数组中[0,i]中非递减序列元素和最大值为prefix[i]，[i,n-1]中非递增序列元素和最大值为suffix[i]，遍历i作为峰顶，最大值即为 max⁡(prefix[i]+suffix[i]−maxHeights[i])

heights[i]=maxHeights[i]

放开对两侧的限制，才能使得prefix[i]和suffix[i]尽可能大；
对于左侧的prefix[i]的求法：

我们保持单调栈中元素是增的，也就是说：
- maxHeights依次入栈，若栈为空直接进入；
- 在maxHeights[i]入栈之前，将所有大于它的栈顶全部弹出；
- 弹出后假设栈顶为maxHeights[j] j<i，我们可以利用已经求好的prefix[j]和j左侧的取值关系，得到prefix[i]=prefix[j]+(i-j)*maxHeights[i],因为在[j+1,i-1]中的值最多取到maxHeights[i]
对于右侧的suffix[i]的求法;

我们把数组反过来入单调栈，求法就和上面一样了;

注意，实际入栈的应该是数组的索引，而不是数组元素，这样方便使用递推关系；

上代码：

long long maximumSumOfHeights(vector<int>& maxHeights) {
        std::stack<int> s,t;
        long long sum = 0;
        int n = maxHeights.size();
        vector<long long> prefix(n);
        vector<long long> suffix(n);
        for(int i=0;i<n;i++){
            if(s.empty()){
                s.push(i);
                prefix[i] = maxHeights[i];
                continue;
            }
            while(!s.empty()&&maxHeights[s.top()]>maxHeights[i]) s.pop();
            if(s.empty()) prefix[i] = (i+1)*1LL*maxHeights[i];
            else prefix[i] = (i-s.top())*1LL*maxHeights[i] + prefix[s.top()];
            s.push(i);
        }
        for(int i=n-1;i>=0;i--){
            if(t.empty()){
                t.push(i);
                suffix[i] = maxHeights[i];
                continue;
            }
            while(!t.empty()&&maxHeights[t.top()]>maxHeights[i]) t.pop();
            if(t.empty()) suffix[i]=(n-i)*1LL*maxHeights[i];
            else suffix[i] = (t.top() - i)*1LL*maxHeights[i] + suffix[t.top()];
            t.push(i);
        }
        for(int i=0;i<n;i++){
            if(sum<prefix[i]+suffix[i]-maxHeights[i]) 
                sum = prefix[i]+suffix[i]-maxHeights[i];
        }
        return sum;
    }

很不应该的一道题，之前的算法学的一点也不扎实，也可能是太久没看算法了（一学期），得回炉重造了；