时间复杂度
O(n)
分析
接着上篇。从左向右依次处理Left，处理Left[i]时，从右向左寻找第一个符合maxHeights[j]<maxHeights[i]的j。如果j1<j2，且maxHeights[j1]>=maxHeights[j2]，那j1永远不会被选到。比如：{1,3,2,4,5}，由于2在3右边，且小于3，则无论如何不会选中3。{1,2,2.....}，后面无论有什么数，都不会选中第一个2，要么是其他数，要么是第二个2。
可以用栈实现，入栈maxHeights[i]之前，先出栈大于等于maxHeights[i]的数，剩余的都小于maxHeights[i]的数。也就是栈按升序排序的。由于maxHeights[i]和heights[i]都可以通过索引查询，栈中只需要记录索引。
Right类似，不再累赘。
样例分析
|
maxHeights |
Left的栈情况 |
|
{1,2,3,4,5} |
1 12 123 1234 12345 |
|
{5,4,3,2,1} |
5 4 3 2 1 |
|
{1,2,4,3,5} |
1 12 124 123 1235 |
|
{3,1,2} |
3 1 12 |
|
{2,1,3} |
2 1 13 |
代码
核心代码
class Solution {
public:
long long maximumSumOfHeights(vector<int>& maxHeights) {
m_c = maxHeights.size();
m_vLeft.resize(m_c);
m_vRight.resize(m_c);
{//处理左边
stack<int> sta;//记录做边的索引
for (int i = 0; i < m_c; i++)
{
const auto& h = maxHeights[i];
while (sta.size() && (maxHeights[()] >= h))
{
sta.pop();//左边比右边大，不会被选中
}
if (sta.size())
{
m_vLeft[i] = m_vLeft[()] + (long long)h * (i - ());
}
else
{
m_vLeft[i] = (long long)h * (i -(-1) );
}
sta.emplace(i);
}
}
{//处理右边
stack<int> sta;//记录做边的索引
for (int i = m_c - 1; i >= 0; i--)
{
const auto& h = maxHeights[i];
while (sta.size() && (maxHeights[()] >= h))
{
sta.pop();//左边比右边大，不会被选中
}
if (sta.size())
{
m_vRight[i] = m_vRight[()] + (long long)h * (()-i);
}
else
{
m_vRight[i] = (long long)h * (m_c-i);
}
sta.emplace(i);
}
}
long long llRet = 0;
for (int i = 0; i < m_c; i++)
{//假定i是山顶
long long llCur = m_vLeft[i] + m_vRight[i] - maxHeights[i];
llRet = max(llRet, llCur);
}
return llRet;
}
int m_c;
vector<long long> m_vLeft, m_vRight;
};测试用代码
class CDebug : public Solution
{
public:
long long maximumSumOfHeights(vector<long long>& maxHeights, vector<long long>& vLeft, vector<long long>& vRight)
{
vector<int> maxs(maxHeights.begin(), maxHeights.end());
long long llRet = Solution::maximumSumOfHeights(maxs);
for (int i = 0 ; i < vLeft.size();i++ )
{
assert(m_vLeft[i] == vLeft[i]);
assert(m_vRight[i] == vRight[i]);
}
//调试用代码
std::cout << "Left: ";
for (int i = 0; i < m_c; i++)
{
std::cout << m_vLeft[i] << " ";
}
std::cout << std::endl;
std::cout << "Right: ";
for (int i = 0; i < m_c; i++)
{
std::cout << m_vRight[i] << " ";
}
std::cout << std::endl;
return llRet;
}
};
int main()
{
vector < vector<vector<long long>>> param = { {{1,2,3,4,5} ,{1,3,6,10,15},{5,8,9,8,5}} ,
{{5,4,3,2,1},{5,8,9,8,5},{15,10,6,3,1}} ,
{{1,2,4,3,5},{1,3,7,9,14},{5,8,10,6,5}},
{{3,1,2}, {3,2,4},{5,2,2}},
{{2,1,3},{2,2,5},{4,2,3}},
{{1000000000,1000000000,1000000000},{1000000000,2000000000,3000000000LL},{3000000000LL,2000000000,1000000000}} };
for (auto& vv : param)
{
auto res = CDebug().maximumSumOfHeights(vv[0], vv[1], vv[2]);
}
//auto res = Solution().maxPalindromes("rire", 3);
//CConsole::Out(res);
}
使用封装类的代码
class CRangIndex
{
public:
template<class _Pr>
CRangIndex(int iVectorSize, _Pr CurIndexCmpStackTopIndex)
{
m_c = iVectorSize;
m_vLeft.assign(m_c, -1);
m_vRight.assign(m_c, m_c);
stack<int> sta;
for (int i = 0; i < m_c; i++)
{
while (sta.size() && (CurIndexCmpStackTopIndex(i, ())))
{
m_vRight[()] = i;
sta.pop();
}
if (sta.size())
{
m_vLeft[i] = ();
}
sta.emplace(i);
}
}
template<class _Pr>
CRangIndex(const vector<int>& nums, _Pr CurValueCmpStackTopValue)
{
m_c = nums.size();
m_vLeft.assign(m_c, -1);
m_vRight.assign(m_c, m_c);
stack<int> sta;
for (int i = 0; i < m_c; i++)
{
while (sta.size() && (CurValueCmpStackTopValue(nums[i], nums[()])))
{
m_vRight[()] = i;
sta.pop();
}
if (sta.size())
{
m_vLeft[i] = ();
}
sta.emplace(i);
}
}
int m_c;
vector<int> m_vLeft, m_vRight;//vLeft[i] 从右向左第一个小于nums[i] ;vRight[i] 是第一个小于等于nums[i]。
};
class Solution {
public:
long long maximumSumOfHeights(vector<int>& maxHeights) {
CRangIndex ri(maxHeights, std::less<>());
m_vLeft.resize(ri.m_c);
for (int i = 0; i < ri.m_c; i++)
{
m_vLeft[i] = (-1 == ri.m_vLeft[i]) ? 0 : m_vLeft[ri.m_vLeft[i]];
m_vLeft[i] += ((long long)i - ri.m_vLeft[i]) * maxHeights[i];
}
m_vRight.resize(ri.m_c);
long long llRet = 0;
for (int i = ri.m_c - 1; i >= 0; i--)
{
m_vRight[i] = (ri.m_c == ri.m_vRight[i]) ? 0 : m_vRight[ri.m_vRight[i]];
m_vRight[i] += ((long long)ri.m_vRight[i] - i ) * maxHeights[i];
long long llCur = m_vLeft[i] + m_vRight[i] - maxHeights[i];
llRet = max(llRet, llCur);
}
return llRet;
}
int m_c;
vector<long long> m_vLeft, m_vRight;
};
