寒假CS精英挑战营_算法部分_第0周_直方图中最大的矩形_笔记

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了寒假CS精英挑战营_算法部分_第0周_直方图中最大的矩形_笔记，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2050字，纯文字阅读大概需要3分钟。

内容图文

一.题目描述

问题描述

有一个直方图，横轴长度为 n，第 i 列的高度为 h[i]。
请你求出在这个直方图中面积最大的子矩阵。

输入格式

第一行一个正整数 n。
第二行 n 个用空格隔开的非负整数，依次描述 h[1],h[2],…,h[n]。

输出格式

输出一行一个数，表示最大面积。

样例输入

5
2 3 3 3 2

样例输出

10

二.几种解题思路

1.暴力

枚举每一条可能的底边，计算出高，求出面积最大值，复杂度$O(n^3)$O(n3)

2.暴力算法邓公版

1)定义曲线上每个极小值点为一个卡位点，记为k（pivot)
2)每个卡位点左右两侧都有挡住他的点（比卡位点小的地方），记为$i_k$ik?和$j_k$jk?，此时围城的矩形的面积为一个极大值，面积为$H[k]*(j_k-i_k-1)$H[k]?(jk??ik??1)
3)枚举每一个卡位点，得到一系列极大值，即可找出矩形的最大值,该算法复杂度$O(n^2)$O(n2)

3.分治算法

定义一个区间最低lo,最高hi，卡位点k。
根据卡位点k，将一个区间划分为左右两侧，返回左区间最大值，右区间最大值和当前区间的值，这三个值中的最大值，递归调用即可得到结果

复杂度分析：

$T(n) = \begin{cases} 2*T(\frac n2) &\text{best} \\ T(n-1) &\text{worst } \end{cases}+O(n)$T(n)={2?T(2n?)T(n?1)?bestworst ?+O(n)因此，最优时达到了O(nlogn),但是最坏情况为$O(n^2)$O(n2)

4.分治+查找表

做一个查找表（look up table),记录每一个区间中的最大值

复杂度分析：

查找:$O(1)$O(1)
构造:$O(n^2)$O(n2)
存储:$O(n^2)$O(n2)
构造和存储太复杂，不可取！

5.分治+线段树

查找:$O(logn)$O(logn)
构造:$O(nlogn)$O(nlogn)
存储:$O(n)$O(n)
通过线段树，分治算法被优化到了O(nlogn)

6.单调栈

从左到右枚举直方图的每一列
维护一个栈底到栈顶高度单调上升的栈
若下一列小于栈顶，则弹出栈顶并更新答案
若下一列大于等于栈顶，则将该列压入栈

三.单调栈

int getAnswer(int n, int *height) {  
    int ans = 0;
    stack<int> mystack;//一个单调栈
    mystack.push(0);//height[0]=0，边界
    //循环到n+1,因为height[n+1]=0，边界
    for (int i = 1; i <= n+1; ++i)
    {
        while (!mystack.empty()&&height[mystack.top()]>height[i]) {
         int nowHeight = height[mystack.top()];
         mystack.pop();
         int L = mystack.empty() ? -1 : mystack.top();
         ans = max(ans, nowHeight*(i-L-1));
     }
     mystack.push(i);
    }
    return ans;
   }

难顶

• 点赞
• 收藏
• 分享
• • 文章举报

陪我到可可西里去看海 发布了2 篇原创文章 · 获赞 1 · 访问量 12 私信 关注

内容总结

以上是互联网集市为您收集整理的寒假CS精英挑战营_算法部分_第0周_直方图中最大的矩形_笔记全部内容，希望文章能够帮你解决寒假CS精英挑战营_算法部分_第0周_直方图中最大的矩形_笔记所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---