单调栈
用栈去掉无用的数据,依次把元素的下标入栈,相同的数字只存储最靠左的第一个下标。每次遍历一个数都与栈顶的元素比较,筛去栈顶中较大的数,减去多余的值,a[j] * (st.top() - j)
;a[j]
是当前塔能达到的最大有效高度,st.top() - j)
是下标的偏移量,刚好就是要删去的a[j]
的个数,删完以后需要把转换成x
高度的值加回来。
哨兵:左右两边设哨兵-1和n - 1,对于第一组数据要特殊处理,同时while循环里要变成 > 1
class Solution {
public:
typedef long long LL;
long long maximumSumOfHeights(vector<int>& a) {
int n = a.size();
vector<LL> suf(n + 1);
stack<int> st;
st.push(n);//哨兵
LL sum = 0;
for (int i = n - 1; i >= 0; i -- ) {
int x = a[i];
while (st.size() > 1 && a[st.top()] >= x) {
int j = st.top();
st.pop();
sum -= (LL)a[j] * (st.top() - j);
}
sum += (LL)x * (st.top() - i);
suf[i] = sum;
st.push(i);
}
LL ans = sum;
st = stack<int>();
st.push(-1);
LL pre = 0;
for (int i = 0; i < n; i ++ ) {
int x = a[i];
while (st.size() > 1 && x <= a[st.top()]) {
int j = st.top();
st.pop();
pre -= (LL)a[j] * (j - st.top());
}
pre += (LL)x * (i - st.top());
ans = max(ans, pre + suf[i + 1]);
st.push(i);
}
return ans;
}
};