代码随想录Day64(一刷完结)

这篇具有很好参考价值的文章主要介绍了代码随想录Day64(一刷完结)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

今天学习单调栈解决最后一道题

84.柱状图中的最大矩形

给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。

求在该柱状图中,能够勾勒出来的矩形的最大面积。

示例 1:

代码随想录Day64(一刷完结)

 

输入:heights = [2,1,5,6,2,3]
输出:10
解释:最大的矩形为图中红色区域,面积为 10

思路:

1.本题初见感觉是类似于Day63的接雨水,但单调栈的思路需要稍微转换一下。

2.相比起前面所有题单调栈是从栈顶到栈尾递增,本题是需要栈顶到栈尾递减才行。至于为什么这么做,相当于我们确定一个矩形的高度作为基准,然后来看他的宽度能延伸到何处(相当于找到左边和右边第一个比自己低的高度,此时就无法继续延伸),进而确定算面积的宽度。

3.但本题还需要考虑一种情况,我们如果完全按照接雨水那道题的步骤去做,会发现当原数组是单调递增或是单调递减时就会出现问题:(1)如果原数组是单调递增,因为我们单调栈是栈顶到栈尾递减,因此此时会一直入栈元素直到遍历完整个数组但却没有进行一次面积计算(因为只有当前元素小于栈顶元素时我们实际上才算找到了一次计算的机会);(2)如果原数组是单调递减,主要涉及到遍历的最初。我们会先将第一个元素压入栈然后从第二个元素开始遍历,但第二个元素比第一个元素小,我们显然需要进行一次计算:以第一个元素为基准,第二个元素是其右边第一个更低的高度,但此时无法找到其左边第一个比自己低的高度

因此为了解决原数组单调的问题,我们在数组首尾各加入一个0,首部加入0解决单调递减时无法找到第一个元素左边第一个比自己低的高度;尾部加入0解决单调递增时不会进行任何一次计算。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int result = 0;
        stack<int> st;
        //在原数组首尾插入一个0防止数组纯单调导致发生问题
        heights.insert(heights.begin(), 0);
        heights.push_back(0);
        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 left = st.top();
                        int right = i;
                        int w = right - left - 1;
                        int h = heights[mid];
                        result = max(result, w * h);
                    }
                }
                st.push(i);
            }
        }

        return result;
    }
};

启发:

1.对于单调栈这一自己完全不熟系的领域,尽管有了前面一些题的基础,套代码的模板是能套了,但要自己捋清楚思路还是有些困难,在接下来一段时间仍需要继续理解。

2.本题用到了两种变化时定一种的思路,这一思路在之前贪心算法中避免同时考虑两种情况导致顾此失彼时有类似的情况,也相当于是进行了一次复习。

最后的最后,感谢代码随想录总结出来的这一套算法试题,经历了两个月的时间终于全部过完了第一遍,尽管还有不少思想方法自己掌握的不算牢固,但相比起之前几乎零基础的自己也已经提升了不少,也巩固了自己许多基础知识,在以后还会进一步对自己薄弱的环节进行重刷和进一步的集中做题来巩固。完结撒花!文章来源地址https://www.toymoban.com/news/detail-430610.html

到了这里,关于代码随想录Day64(一刷完结)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 代码随想录day59

    647. 回文子串 给你一个字符串  s  ,请你统计并返回这个字符串中  回文子串  的数目。 回文字符串  是正着读和倒过来读一样的字符串。 子字符串  是字符串中的由连续字符组成的一个序列。 具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不

    2024年02月07日
    浏览(49)
  • 代码随想录Day62

    今天继续学习单调栈解决相关问题。 nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。 给你两个 没有重复元素 的数组 nums1 和 nums2 ,下标从 0 开始计数,其中nums1 是 nums2 的子集。 对于每个 0 = i nums1.length ,找出满足 nums1

    2024年02月01日
    浏览(56)
  • 代码随想录day01

    ● 思维不难,主要是考察对代码的掌控能力 ● 内存中的存储方式:存放在连续内存空间上的相同类型数据的集合 ● 数组可以通过下标索引获取到下标对应的数据 ● 数组下标从0开始 ● 因为内存空间地址连续,因此删除或增加元素的时候,难免移动其他元素地址 ● Java中的

    2024年02月13日
    浏览(58)
  • 代码随想录Day50

    昨天因为准备面试所以咕咕了一天。今天继续学习动规算法,尽管背包问题已经结束但其中的各类思想仍需要进一步理解。 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两

    2023年04月14日
    浏览(56)
  • 【代码随想录】刷题Day47

    198. 打家劫舍 1.dp数组含义:dp[i]为i位置下的最大能得到的价值 2.根据条件:相邻不能偷。i位置的最大价值取决于i-1位置是否已经偷过了。如果偷过了,i位置的最大价值就是dp[i-1],即i位置的物品不偷;如果没有偷过,i位置的最大价值就是dp[i-2]+nuvms[i],i位置的数和对应的d

    2024年02月07日
    浏览(49)
  • 代码随想录day42(背包)

    2024年02月13日
    浏览(37)
  • 【代码随想录】刷题Day31

    455. 分发饼干 贪心的思路就是:小的饼干尽量去匹配胃口小的孩子,这样才能实现尽可能多孩子吃到。 那么代码就很好写了: 1.排序g和s,这样方便查找小的数 2.饼干的位置不停遍历,对应我们需要一个ret代表当前孩子位置 3.如果当前位置为孩子的数量,说明ret记录下所有的

    2024年02月06日
    浏览(50)
  • 【代码随想录】刷题Day36

    435. 无重叠区间 先从小到大排序,其实本题依然是求出共同区域,只不过题目需要我们删除尽量少的区间。所以我们需要删除的一定是范围跨度大的并且跟其他有公共区间的区域。所以每次更新右边范围都需要考虑最小的范围。 1.if(intervals[i][0]end),说明有重复的区间,那么我

    2024年02月07日
    浏览(58)
  • 代码随想录day7

    目录 第454题.四数相加II 思路: 383. 赎金信 思路: 第15题. 三数之和 思路: 力扣题目链接 给你四个整数数组 nums1、nums2、nums3 和 nums4 ,数组长度都是 n ,请你计算有多少个元组 (i, j, k, l) 能满足: 0 = i, j, k, l n nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0   示例 1: 输入:nums1 = [1,2

    2024年02月10日
    浏览(41)
  • 代码随想录day6

    一开始想着构建两个hash表,但如果后面字符串长的可能会超时 这里借用数组构建hash表,主要思想是26个字母组成的数组统计出现次数 如果有出现次数为非0,则说明有问题,可以加以利用作为判断条件 这里对乱序的子字符串先排序,排序后的结果是否一致可以作为分组的依

    2024年02月04日
    浏览(56)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包