美丽塔单调栈O(n)解法

// maximumSumOfHeights2.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。 // #include <iostream> #include <vector> #include <map> #include<stack> #include <assert.h> using namespace std; 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[sta.top()] >= h)) { sta.pop();//左边比右边大，不会被选中 } if (sta.size()) { m_vLeft[i] = m_vLeft[sta.top()] + (long long)h * (i - sta.top()); } 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[sta.top()] >= h)) { sta.pop();//左边比右边大，不会被选中 } if (sta.size()) { m_vRight[i] = m_vRight[sta.top()] + (long long)h * (sta.top() - 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); }