代码随想录 | Day 60(完结) - LeetCode 84. 柱状图中最大的矩形
admin
2024-04-10 06:26:02
0次

        今天是单调栈的最后一天,延续了昨天的接雨水问题。只有一道题,同样3种解法。其中DP和单调栈解法难度都有提升,都需要对两端元素做特殊处理。重点是以前面的接雨水问题为模板,理解下这类问题的“左、中、右柱子确定矩形”的方法。另外今天也是最后一天了,紧紧张张也算赶上了,这60天虽然不容易,但也一转眼就过去了,完结撒花~


        第1题(LeetCode 84. 柱状图中最大的矩形)与day 59中第2题(LeetCode 42. 接雨水)很相似,同样有双指针、DP、单调栈这3种解法。

        双指针法相比接雨水,主要是从“找左、右两边各自最高的柱子”变成了“要找左、右两边各自第一个比当前柱子小的位置”,使其分别作为左、右边界(不包含在内),再令当前柱子的高作为矩形的高,两者相乘得到当前位置的矩形大小。所以在内部循环找“第一个比当前柱子小的位置”时,要先将柱子大小初始化为当前柱子高度,然后向左/右移动直至遇到更小值为止。当然,同样因为时间复杂度时O(n²),所以会超时。

// 双指针
class Solution {
public:int largestRectangleArea(vector& heights) {int ans = 0;for (int i = 0; i < heights.size(); ++i) {int indLeft = i, indRight = i;while (indLeft >= 0 && heights[indLeft] >= heights[i]) {--indLeft;}while (indRight < heights.size() && heights[indRight] >= heights[i]) {++indRight;}int w = indRight - indLeft - 1, h = heights[i];ans = max(ans, w * h);}return ans;}
};

        DP解法也与接雨水类似。由于最后矩形的宽是两下标之差再减1,所以这一题的难度主要增加在“dp数组要记录下标而不是柱子高度”。具体来说,两个p数组,indSmallerLeft[i],indSmallerRight[i]分别代表位置i左、右两边第一个小于i位置柱子高度的柱子下标。所以对于位置i,其indSmallerLeft值就需要从(i - 1)开始不断通过indSmallerLeft表向左跳转,直到找到更小值(到0为止),其indSmallerRight值就需要从(i + 1)开始不断通过indSmallerRight表向右跳转,直到找到更小值(到heights表末尾为止)。

        初始化方面,indSmallerLeft和indSmallerRight需要分别初始化第0位和末尾位。第0位的左边界(不包含在内)应该是-1,末尾位的右边界(不包含在内)应该是“末尾 + 1”,所以indSmallerLeft[0]和indSmallerRight[height.size() - 1]分别初始化为-1和height.size()。indSmallerLeft和indSmallerRight在内层循环中需要使用while()。

// DP
class Solution {
public:int largestRectangleArea(vector& heights) {vector indSmallerLeft(heights.size()), indSmallerRight(heights.size());indSmallerLeft[0] = -1;for (int i = 1; i < heights.size(); ++i) {int j = i - 1;while (j >= 0 && heights[j] >= heights[i]) {j = indSmallerLeft[j];}indSmallerLeft[i] = j;}indSmallerRight[heights.size() - 1] = heights.size();for (int i = heights.size() - 2; i >= 0; --i) {int j = i + 1;while (j < heights.size() && heights[j] >= heights[i]) {j = indSmallerRight[j];}indSmallerRight[i] = j;}int ans = 0;for (int i = 0; i < heights.size(); ++i) {int w = indSmallerRight[i]- indSmallerLeft[i] - 1, h = heights[i];ans = max(ans, w * h);}return ans;}
};

        单调栈解法相比接雨水有3点不同:

  1. 栈从单调递减改为单调递增;
  2. 矩形的高度需要更改为中间柱子的高度;
  3. 接雨水问题中,左右两个端点的柱子永远不会有雨水,所以不会成为中间柱子。但这一题的左、右端点也可能成为中间柱子。然而此时左、右柱子右不存在。为此,要在heights前、后分别插入高度为0的柱子;
// 单调栈
class Solution {
public:int largestRectangleArea(vector& heights) {heights.insert(heights.begin(), 0); // 数组头部加入元素0heights.push_back(0); // 数组尾部加入元素0int ans = 0;stack st;st.push(0);for (int i = 1; i < heights.size(); ++i) {if (heights[i] > heights[st.top()]) {st.push(i);}else if (heights[i] == heights[st.top()]) {// st.pop();st.push(i);}else {while (!st.empty() && heights[i] < heights[st.top()]) {int mid = st.top();st.pop();if (!st.empty()) {int w = i - st.top() - 1;int h = heights[mid];ans = max(ans, w * h);}}st.push(i);}}return ans;}
};

相关内容

热门资讯

蜻蜓订购APP贵金属订购非法期...   蜻蜓订购APP以"投资平台"名义对外宣传,主打贵金属期货(订购)交易。该平台一方面强调自身"正规...
悟空订购APP非法期货交易欺骗...   近期,有投资者反映,“悟空订购APP”等平台以白银、贵金属订购为名,宣传所谓“高收益”“低门槛”...
小赢淘金APP期货投资骗局,平...   “小赢淘金”之流,最擅长的就是用“注册送现金”、“充值返券”的糖衣炮弹来引流。别天真地以为那是福...
八方淘金APP非法期货交易欺骗...   警惕!八方生财、每日淘金、小赢淘金、悟空订购、蜻蜓订购、斗金订购等APP均涉嫌非法期货交易!  ...
智易购APP贵金属订购交易骗局...   很多人看到“3元起投”“充值送福利”“操作简单”“随时提现”这类宣传,很容易把智易购APP当成普...
喜玛银庄APP商品订购投资骗局...   喜玛银庄APP白银、铂金“现货订购”骗局警示:无资质平台涉嫌非法期货交易,投资者爆仓后如何维权?...
吉鑫乐享APP炒贵金属订购交易...   近期,多名投资者反映在“吉鑫乐享APP”进行贵金属投资时遭遇严重亏损,甚至血本无归。看似正规的“...
易掘金APP虚假期货投资骗局,...   “易掘金”的APP它打着“高收益、灵活投资”的旗号,宣称通过“商品订购”就能轻松赚钱,吸引了不少...
在大吉订购APP订购交易亏损被...   近期,不少投资者反映在“大吉订购App”上投资白银、铂金等商品遭遇严重亏损。该平台宣称提供现货订...
铂银壹号APP商品订购交易亏损...   许多中小投资者误以为网上的“商品现货订购”是合规合法的理财渠道,殊不知这背后隐藏着巨大的合规风险...
兴鑫淘金APP贵金属订购交易亏...   白银、贵金属或其他商品类投资,除国家批准的正规期货交易场所及持牌期货公司外,市面上大量第三方交易...
铂银掘金APP无资质的违规平台...   铂银掘金等平台的投资者,往往是被“注册送现金”“充值返现券”“首单免亏”等广告话术吸引,进而下载...
八方淘金APP订购交易不合规,...   “八方淘金APP”“铂银掘金APP”“铂银壹号APP”等软件被指以“现货订购”为名,实际采用高杠...
在指尖订购APP订购商品亏损被...   指尖订购APP这类平台,表面是“订购交易”,实则是披着电商外衣的非法期货陷阱。绝大多数投资者被蒙...
在犀贝易购APP做商品订购交易...   市面上打着“现货投资”“贵金属交易”旗号的APP并不少,但真正合规、受监管的平台并不多。犀贝易购...
易达淘金APP虚假商品订购交易...   易达淘金APP存在严重的虚假宣传与违规交易行为。该平台打着“商品订购”的旗号,实则通过不合规的交...
大浪淘金APP白银订购亏损被骗...   大浪淘金APP最隐蔽的套路,在于其完全封闭的内盘交易系统。表面上,它宣称与国际贵金属市场接轨;实...
一品好购APP上订购白银出现亏...   一品好购APP原名“一品订购”,运营方为上海宝智未来信息技术有限公司。近期不少投资者反映在该平台...
九州订购APP贵金属订购投资骗...   九州订购APP正通过抖.音、快手、今日头条等平台大量投放投资广告,用“5元起投”“充值返现”“0...
坚锅淘金APP交易软件并不正规...   当前,市面上大量所谓的“现货商城订购”交易软件,早已偏离了正常的实物商品买卖,演变为高杠杆、高手...