題目

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

時間復雜度

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[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);
}

測試環境

Win10,VS2022 C++17

下載

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

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