题目
给你一个长度为 n 下标从 0 开始的整数数组 maxHeights 。你的任务是在坐标轴上建 n 座塔。第 i 座塔的下标为 i ，高度为 heights[i] 。
如果以下条件满足，我们称这些塔是 美丽 的：
1 <= heights[i] <= maxHeights[i]
heights 是一个 山状 数组。
如果存在下标 i 满足以下条件，那么我们称数组 heights 是一个 山状 数组：
对于所有 0 < j <= i ，都有 heights[j - 1] <= heights[j]
对于所有 i <= k < n - 1 ，都有 heights[k + 1] <= heights[k]
请你返回满足 美丽塔 要求的方案中，高度和的最大值 。
时间复杂度
O(nlogn)
典型样例分析
当i是山顶时，Left[i]记录[0,i]的最大高度和，Right[i]记录[i,n)的最大高度和。
笨办法
由于赛场时间紧，压力大。所以只想到一个笨办法。从小到处理最大高度。下面以Left[i]为例来说明。如果不存在j(0<=j<i)使得maxHeight[j] < maxHeight[i] ,那么[0,i]的高度全为)maxHeight[i]，如{5,4,3,2,1};如果只存在唯一的j，则[0,j]高度不变，(j,i]的高度为maxHeight[i],如{3,1,2}。如果存在多个j，以j最大的为准,如{2,1,3}。如果maxHeight[j] == maxHeight[i]，则height[j]变和不变的结果都一样。
代码
核心代码
class Solution { public: long long maximumSumOfHeights(vector<int>& maxHeights) { m_c = maxHeights.size(); std::multimap<int, int> mHeightIndex; for (int i = 0; i < m_c; i++) { mHeightIndex.emplace(maxHeights[i], i); } for (const auto& [h, i] : mHeightIndex) { {//计算m_mLeft auto it = m_mLeft.lower_bound(i); if (m_mLeft.begin() == it) { m_mLeft[i] = (long long)h * (i + 1); } else { auto pre = std::prev(it); m_mLeft[i] = pre->second + (long long)h * (i - pre->first); } } {//计算m_mRight auto it = m_mRight.upper_bound(i); if (m_mRight.end() == it) { m_mRight[i] = (long long)h * (m_c - i); } else { m_mRight[i] = (long long)it->second + (long long)h * (it->first - i); } } } long long llRet = 0; for (int i = 0; i < m_c; i++) {//假定i是山顶 long long llCur = m_mLeft[i] + m_mRight[i] - maxHeights[i]; llRet = max(llRet, llCur); } return llRet; } int m_c; std::map<int, long long> m_mLeft, m_mRight; };
测试用代码
class CDebug : public Solution { public: long long maximumSumOfHeights( vector<int>& maxHeights, vector<int>& vLeft, vector<int>& vRight) { long long llRet = Solution::maximumSumOfHeights(maxHeights); for (const auto& it : m_mLeft) { assert(it.second == vLeft[it.first]); } for (const auto& it : m_mRight) { assert(it.second == vRight[it.first]); } //调试用代码 std::cout << "Left: "; for (int i = 0; i < m_c; i++) { std::cout << m_mLeft[i] << " "; } std::cout << std::endl; std::cout << "Right: "; for (int i = 0; i < m_c; i++) { std::cout << m_mRight[i] << " "; } std::cout << std::endl; return llRet; } }; int main() { vector < vector<vector<int>>> 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}} }; 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博客
源码及测试用例
https://download.csdn.net/download/he_zhidan/88370053
其它
视频课程
如果你觉得复杂，想从简单的算法开始，可以学习我的视频课程。
https://edu.csdn.net/course/detail/38771
我的其它课程
https://edu.csdn.net/lecturer/6176
测试环境
win7 VS2019 C++17 或Win10 VS2022 Ck++17
相关下载
算法精讲《闻缺陷则喜算法册》doc版
