題目

見上一篇：?較難算法美麗塔時間復(fù)雜度O(n)-CSDN博客

時間復(fù)雜度

O(n)

分析

接著上篇。從左向右依次處理Left，處理Left[i]時，從右向左尋找第一個符合maxHeights[j]<maxHeights[i]的j。如果j1<j2，且maxHeights[j1]>=maxHeights[j2]，那j1永遠(yuǎn)不會被選到。比如：{1,3,2,4,5}，由于2在3右邊，且小于3，則無論如何不會選中3。{1,2,2.....}，后面無論有什么數(shù)，都不會選中第一個2，要么是其他數(shù)，要么是第二個2。
可以用棧實現(xiàn)，入棧maxHeights[i]之前，先出棧大于等于maxHeights[i]的數(shù)，剩余的都小于maxHeights[i]的數(shù)。也就是棧按升序排序的。由于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[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]);
?? ??? ?}

?? ??? ?//調(diào)試用代碼
?? ??? ?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);
}

測試環(huán)境

Win10,VS2022 C++17

下載

源碼：?【免費】美麗塔單調(diào)棧O(n)解法資源-CSDN文庫

doc 講解排版好：【免費】聞缺陷則喜算法冊（9月24增加美麗塔）資源-CSDN文庫