代码随想录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模板网!

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

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

相关文章

  • 代码随想录day02

    ● 力扣题目链接 ● 给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。 思路 ● 暴力排序,时间复杂度O(n + nlogn) ● 使用双指针,时间复杂度O(n) 代码 ● 力扣题目链接 ● 给定一个含有 n 个正整数的数组和一个正整

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

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

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

    20. 有效的括号   思路:这里用模拟栈的方法会更好理解,也就是我们每次遇到朝左方向的三种类型的时候,就加入相反方向的右括号到result栈中。由于栈是一个先进后出的方式,所以我们会有一个判断stack当前为不为空,和stack[-1]是不是和当前循环到的括号相同。如果说相同

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

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

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

    目录 344.反转字符串 思路: 541. 反转字符串II 思路: 题目:剑指Offer 05.替换空格 思路: 151.翻转字符串里的单词 思路: 题目:剑指Offer58-II.左旋转字符串 思路: 力扣题目链接(opens new window) 编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形

    2024年02月09日
    浏览(44)
  • 代码随想录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日
    浏览(38)
  • 代码随想录day6

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

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

    2024年02月13日
    浏览(33)
  • 【代码随想录】刷题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日
    浏览(43)
  • 【代码随想录】刷题Day36

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

    2024年02月07日
    浏览(51)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包