当前位置：首页 > news >正文

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

news 2025/8/28 1:51:09

题目

见上一篇：较难算法美丽塔时间复杂度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);