高端网站建设设计,百度推广云南总代理,高端设计网站平台,创意设计网站公司Tag
【单调栈】【数组】【2023-12-21】 题目来源
2866. 美丽塔 II 题目解读
题目意思相对明确#xff0c;所谓的美丽塔数组就是山状数组#xff0c;即有一个高度为 maxHeight[i] 的山峰#xff0c;山峰两侧的高度要小于 maxHeight[i] 并且小于各自的允许高度。需要找出满…Tag
【单调栈】【数组】【2023-12-21】 题目来源
2866. 美丽塔 II 题目解读
题目意思相对明确所谓的美丽塔数组就是山状数组即有一个高度为 maxHeight[i] 的山峰山峰两侧的高度要小于 maxHeight[i] 并且小于各自的允许高度。需要找出满足以上条件的美丽塔数组返回数组和。 方法一暴力枚举
暴力枚举即以每一个整数元素作为山峰对左右两侧的山峰高度依次处理取出所有山峰中美丽塔数组的最大值。处理规则如下
当前的最高山峰下标为 i此处山峰高度为 maxHeight[i]当前山峰美丽塔的最大值为 res maxHeight[i]从下标 i-1 处开始枚举山峰左侧的高度 maxHeight[i-1]如果 maxHeight[i-1] maxHeight[i]则下标 i-1 处的山峰高度最大为 maxHeight[i-1]否则下标 i-1 处的山峰高度最大为 maxHeight[i]其实 i-1 处的山峰高度最大为 min(maxHeight[i-1], maxHeight[i])。加到 res 中枚举完山峰 i 左侧的山即可得到以下标 i 为山峰的左侧山的高度最大值。同理可以得到以下标 i 为山峰的右侧山的高度最大值。最后选出枚举所有山峰得到的最大值作为最后的答案。
复杂度分析
时间复杂度 O ( n 2 ) O(n^2) O(n2) n n n 为数组 maxHeight 的长度对于规模为 1 0 3 10^3 103 甚至 1 0 4 10^4 104 的数据量该方法可以顺利通过对于更大规模的数据比如 1 0 5 10^5 105暴力枚举的方法一定超时时间复杂度 O ( n ) O(n) O(n) 的解法请看 方法二。
空间复杂度 O ( 1 ) O(1) O(1)。
方法二前后缀分解单调栈
前、后缀的方法在做题时候想到了但是一直没想通如何计算前、后缀经过 前后缀分解单调栈Python/Java/C/Go 思路点拨之后豁然开朗。
把 maxHeight 简化为 nums。
我们可以借助前后缀的思想提前计算山峰左侧的递增段的最大和以及山峰右侧递减段最大和。
我们使用数组 pre[i] 表示山峰 nums[i] 左侧的递增段的最大和使用数组 suf[i] 表示山峰右侧递减段最大和。那么最终的答案为 pre[i] suf[i1] 的最大值。
接下来看一下如何计算数组 pre 和 suf。
使用单调栈元素值从栈底到栈顶严格递增。
我们先计算 pre从左到右遍历数组 nums设当前的元素和为 sum。
如果 nums[i] 大于栈顶元素直接将 nums[i] 加到 sum 中同时把 i 入栈栈中只需要保存下标否则只要 nums[i] 小于等于栈顶的元素值就不断循环撤销掉原先加入到 sum 中的值。循环结束后从 nums[i] 到 nums[j-1]假设现在的栈顶下标是 j 的值都必须是 nums[i]把 nums[i] * (j - i) 加到 sum 中。
现在以数组 nums [5, 3, 4, 1, 1] 为例用图示来模拟上述计算 pre[i] 的过程。
1初始化单调栈 st并放入哨兵 -1
2遍历数组 nums 开始计算当前 i 0栈 s 的长度为 1 不满足大于 1 的要求跳过 while 循环计算当前和 sum 0 nums[i] * (i - st.top()) 5 * (0 - (-1)) 5更新 pre[0] 5将 0 加入单调栈 st 中。
3i 1执行 while 循环st 弹出 0撤销 sum 中的 5 即 sum 5 - 5 0当前和 sum 0 3 * (1 - (-1)) 6更新 pre[1] 6将 1 加入单调栈 st 中。
4i 2不需要执行 while 循环当前和 sum 4 3 * (2 - 1) 10更新 pre[2] 10将 2 加入单调栈 st 中。
5i 3执行 while 循环st 弹出 2先撤销 sum 中的 4 即 sum 10 - 4 6接着弹出 1 并撤销 sum 中的 2 个 3 即 sum 6 - 2 * 3 0当前和 sum 0 1 * (3 - (-1)) 4更新 pre[3] 4将 3 加入单调栈 st 中。
6i 4执行 while 循环st 弹出 3撤销 sum 中的 4 个 1 即 sum 4 - 1 * (3 - (-1)) 0当前和 sum 0 1 * (4 - (-1)) 5更新 pre[4] 5将 1 加入单调栈 st 中。
7数组 pre 计算完成pre[i] [5, 6, 10, 4, 5]。
数组 suf 的计算同理这时候需要从右往左遍历。
实现代码
class Solution {
public:long long maximumSumOfHeights(vectorint nums) {int n nums.size();vectorlong long pre(n), suf(n1);stackint st;st.push(-1); // 哨兵long long sum 0;for (int i 0; i n; i) {int x nums[i];while (st.size() 1 x nums[st.top()]) {int j st.top();st.pop();sum - (long long) nums[j] * (j - st.top());}sum (long long) x * (i - st.top());pre[i] sum;st.push(i);}st stackint(); sum 0;st.push(n); // 哨兵for (int i n-1; i 0; --i) {int x nums[i];while (st.size() 1 x nums[st.top()]) {int j st.top();st.pop();sum - (long long) nums[j] * (st.top() - j);}sum (long long) x * (st.top() - i);suf[i] sum;st.push(i);}long long res 0;for (int i 0; i n; i) {res max(res, pre[i] suf[i1]);}return res;}
};复杂度分析
时间复杂度 O ( n ) O(n) O(n) n n n 为数组 nums 的长度。
空间复杂度 O ( n ) O(n) O(n)使用的额外空间为记录山峰左侧的最大和。
