【每日一题】美丽塔 II
Tag
【单调栈】【数组】【2023-12-21】
题目来源
|
题目解读
题目意思相对明确,所谓的美丽塔数组就是山状数组,即有一个高度为 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[i+1]
的最大值。
接下来看一下如何计算数组 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
中。
(3)i = 1
:执行 while
循环,st
弹出 0
,撤销 sum
中的 5
即 sum = 5 - 5 = 0
;当前和 sum = 0 + 3 * (1 - (-1)) = 6
;更新 pre[1] = 6
,将 1
加入单调栈 st
中。
(4)i = 2
:不需要执行 while
循环;当前和 sum = 4 + 3 * (2 - 1) = 10
;更新 pre[2] = 10
,将 2
加入单调栈 st
中。
(5)i = 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
中。
(6)i = 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(vector<int>& nums) {
int n = nums.size();
vector<long long> pre(n), suf(n+1);
stack<int> 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 = stack<int>(); 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[i+1]);
}
return res;
}
};
复杂度分析
时间复杂度:
O
(
n
)
O(n)
O(n),
n
n
n 为数组 nums
的长度。
空间复杂度: O ( n ) O(n) O(n),使用的额外空间为记录山峰左侧的最大和。
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!