小众写作网站,关于友谊的连接,网页设计与制作前景如何,惠州软件开发题目
见上一篇#xff1a; 较难算法美丽塔时间复杂度O(n)-CSDN博客
时间复杂度
O(n)
分析
接着上篇。从左向右依次处理Left#xff0c;处理Left[i]时#xff0c;从右向左寻找第一个符合maxHeights[j]maxHeights[i]的j。如果j1j2#xff0c;且maxHeights[j1] 较难算法美丽塔时间复杂度O(n)-CSDN博客
时间复杂度
O(n)
分析
接着上篇。从左向右依次处理Left处理Left[i]时从右向左寻找第一个符合maxHeights[j]maxHeights[i]的j。如果j1j2且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(vectorint maxHeights) {m_c maxHeights.size();m_vLeft.resize(m_c);m_vRight.resize(m_c);{//处理左边stackint 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);}}{//处理右边stackint 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;vectorlong long m_vLeft, m_vRight;
};
测试用代码
class CDebug : public Solution { public: long long maximumSumOfHeights(vectorlong long maxHeights, vectorlong long vLeft, vectorlong long vRight) { vectorint 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 vectorvectorlong 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 C17
下载
源码 【免费】美丽塔单调栈O(n)解法资源-CSDN文库
doc 讲解排版好【免费】闻缺陷则喜算法册9月24增加美丽塔资源-CSDN文库
