做书app下载网站有哪些,怎样建设微网站首页,免费快速建站网站,玉树市wap网站建设公司Day60 84.柱状图中最大的矩形刷题总结 84.柱状图中最大的矩形
题目链接#xff1a;84.柱状图中最大的矩形 遍历每个元素#xff0c;找到左右元素小于当前元素的#xff0c;以左右元素间的区间#xff08;左开右开区间#xff09;所围成的面积中的最大值。
数组尾部加一个… Day60 84.柱状图中最大的矩形刷题总结 84.柱状图中最大的矩形
题目链接84.柱状图中最大的矩形 遍历每个元素找到左右元素小于当前元素的以左右元素间的区间左开右开区间所围成的面积中的最大值。
数组尾部加一个0由于单调栈为单调递减当前元素是在数组元素小于栈顶元素的情况下才开始弹出的为了避免栈不弹出数组默认顺序为单调递增则不会弹出因此栈尾需要给一个一定会弹出的数字因此为0。 确保所有的柱子都能被处理到因为如果柱子的高度都是递增的那么最后一个柱子可能不会被处理到。
数组首部也需要加一个0因为小于元素左侧的为栈顶第二元素也就是为了防止对空栈进行操作如果栈为空则表示当前柱子是最小的柱子。但对于vector数组来说在首部插入元素很消耗时间因此可以单独对空栈进行判断从而避免在首部插入元素。
class Solution {
public:int largestRectangleArea(vectorint heights) {heights.push_back(0);//数组尾部加0stackint st;int sum 0;for (int i 0; i heights.size(); i) {while (!st.empty() heights[i] heights[st.top()]) {int cur st.top();st.pop();int Width st.empty() ? i/*当栈为空时直接输出i作为宽度*/ : i - st.top() - 1;sum max(sum, Width * heights[cur]);}st.push(i);}return sum;}
};刷题总结
这60天过得飞快。我已养成每天打开CLion、《代码随想录》、B站和CSDN的习惯。刷题不仅让我对数据结构、算法等相关知识有了更深入的了解还提升了我对C的使用能力。
每次观看完视频讲解后我都会亲自动手编写代码并将其与文章中给出的代码进行比较从中吸取双方的优点。借助CLion上的LeetCode插件我对编译器调试功能运用得也更加娴熟。
最重要的是我学会了对问题进行切入点分析。按照《代码随想录》的刷题顺序进行学习这种连贯性的方式让我更容易抓住重点不再东奔西跑极大地提高了我的做题效率。回头看刷卡记录每一天都有新的收获这种满足感弥足珍贵。
