算法刷题Day 59 下一个更大元素II+接雨水

这篇具有很好参考价值的文章主要介绍了算法刷题Day 59 下一个更大元素II+接雨水。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

Day 59 单调栈

503. 下一个更大元素II

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int len = nums.size();
        nums.insert(nums.end(), nums.begin(), nums.end());

        vector<int> descStk, rst(len, -1);

        for (int i = 0; i < nums.size(); ++i)
        {
            while (!descStk.empty() && nums[descStk.back()] < nums[i])
            {
                int idx = descStk.back() % len;
                if (rst[idx] == -1)
                {
                    rst[idx] = nums[i];
                }
                descStk.pop_back();
            }
            descStk.push_back(i);
        }

        return rst;
    }
};

其实也可以不扩充nums,而是在遍历的过程中模拟走了两边nums

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int len = nums.size();
        vector<int> descStk, rst(len, -1);

        for (int i = 0; i < len * 2; ++i)
        {
            int modI = i % len;
            while (!descStk.empty() && nums[descStk.back()] < nums[modI])
            {
                int idx = descStk.back() % len;
                if (rst[idx] == -1)
                {
                    rst[idx] = nums[modI];
                }
                descStk.pop_back();
            }
            descStk.push_back(modI);
        }

        return rst;
    }
};

42. 接雨水

三种方法都写了一遍

暴力方法

逐列计算

找到当前位置,左边最高的柱子的索引和右边最高的柱子的索引,两者中相对小的那个,将去当前位置的高度,就是水柱的高度,而宽度是1

超时了

class Solution {
public:
    int trap(vector<int>& height) {
        int sum = 0;

        for (int i = 1; i < height.size() - 1; i++)
        {
            int leftTaller, rightTaller;
            leftTaller = rightTaller = height[i];

            for (int j = i - 1; j >= 0; --j)
            {
                if (height[j] > leftTaller)
                {
                    leftTaller = height[j];
                }
            }

            for (int j = i + 1; j < height.size(); ++j)
            {
                if (height[j] > rightTaller)
                {
                    rightTaller = height[j];
                }
            }

            sum += min(leftTaller, rightTaller) - height[i];
        }

        return sum;
    }
};

双指针

提前记录好左边最高的和右边最高的索引

class Solution {
public:
    int trap(vector<int>& height) {
        vector<int> maxLeft(height.size()), maxRight(height.size());
        maxLeft[0] = height[0];

        for (int i = 1; i < height.size(); ++i)
        {
            maxLeft[i] = max(height[i], maxLeft[i - 1]);
        }

        maxRight.back() = height.back();        
        for (int i = height.size() - 2; i >= 0; --i)
        {
            maxRight[i] = max(height[i], maxRight[i + 1]);
        }

        int sum = 0; 
        for (int i = 1; i < height.size() - 1; i++)
        {
            sum += min(maxLeft[i], maxRight[i]) - height[i];
        }

        return sum;
    }
};

暴力方法和双指针都是按照列的方式进行计算的

单调栈

而单调栈的方式是按照行的方式进行计算的,在思考的时候要记得这一点区别文章来源地址https://www.toymoban.com/news/detail-624036.html

class Solution {
public:
    int trap(vector<int>& height) {
        int sum = 0;
        stack<int> stk;
        stk.push(0);

        for (int i = 0; i < height.size(); ++i)
        {
            if (height[i] < height[stk.top()])
            {
                stk.push(i);
            }
            else if (height[i] == height[stk.top()])
            {
                stk.pop();
                stk.push(i);
            }
            else
            {
                while (!stk.empty() && height[i] > height[stk.top()])
                {
                    int idx = stk.top();
                    stk.pop();
                    if (!stk.empty())
                    {
                        int w = i - stk.top() - 1;
                        int h = min(height[i], height[stk.top()]) - height[idx];
                        sum += w * h;
                    }
                }
                stk.push(i);
            }
        }

        return sum;
    }
};

到了这里,关于算法刷题Day 59 下一个更大元素II+接雨水的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【力扣】503. 下一个更大元素 II <单调栈>

    给定一个循环数组 nums ( nums[nums.length - 1] 的下一个元素是 nums[0] ),返回 nums 中每个元素的 下一个更大元素 。数字 x 的 下一个更大的元素 是按数组遍历顺序,这个数字之后的第一个比它更大的数,这意味着你应该循环地搜索它的下一个更大的数。如果不存在,则输出 -1

    2024年02月12日
    浏览(41)
  • leetcode503. 下一个更大元素 II 单调栈

    思路: 与之前 739、1475 单调栈的问题如出一辙,唯一不同的地方就是对于遍历完之后。栈中元素的处理,之前的栈中元素因无法找到符合条件的值,直接加入vector中。而这里需要再重头遍历一下数组,找是否有符合条件的,如果仍然找不到的话,才会把它赋值然后加入vecto

    2024年02月11日
    浏览(36)
  • 力扣题库刷题笔记496-下一个更大元素

    1、题目如下: 2、个人Python代码实现   代码如下: class Solution:     def nextGreaterElement(self, nums1: List[int], nums2: List[int]) - List[int]:         #空列表用于输出结果         ans = []         for i in nums1:             #如果nums2中不包含或者最后一位元素为当

    2023年04月26日
    浏览(39)
  • Day58|leetcode 739. 每日温度、496.下一个更大元素 I

    今天开始单调栈! 题目链接:739. 每日温度 - 力扣(LeetCode) 视频链接:单调栈,你该了解的,这里都讲了!LeetCode:739.每日温度_哔哩哔哩_bilibili 题目概述   给定一个整数数组  temperatures  ,表示每天的温度,返回一个数组  answer  ,其中  answer[i]  是指对于第  i  天,下

    2024年02月09日
    浏览(36)
  • 力扣算法刷题Day59|单调栈

    力扣题目:# 503.下一个更大元素II  刷题时长:参考题解后2min 解题方法:单调栈 复杂度分析 时间O(n) 空间O(n) 问题总结 如何解决环的问题 本题收获 循环数组解决方案 思路一:将两个nums数组拼接在一起,使用单调栈计算出每一个元素的下一个最大值,最后再把结果集即res

    2024年02月13日
    浏览(84)
  • 算法训练 Day 2 | 数组:977.有序数组的平方,209.长度最小的子数组,59.螺旋矩阵II

    977. 有序数组的平方 第一想法:暴力破解 看完题解想法:朝着双指针方向想 遇到困难: 用双指针的话,一开始想到两边指针往中间靠,逐个将最大值赋给结果数组。和题解不同的是,循环条件我写了  while (left != right) {...} ,相比于题解的  while (left = right) {...} ,我需要在后

    2023年04月12日
    浏览(47)
  • 算法刷题Day 39 不同路径+不同路径II

    递归(深搜) 使用递归的方法超时(可以过37个case) 来分析一下时间复杂度,这个深搜的算法,其实就是要遍历整个二叉树。 这棵树的深度其实就是m+n-1(深度按从1开始计算)。 那二叉树的节点个数就是 2^(m + n - 1) - 1。可以理解深搜的算法就是遍历了整个满二叉树(其实没

    2024年02月12日
    浏览(46)
  • 算法刷题Day 28 复原IP地址+子集+子集II

    我的做法有点奇怪,还是参考一下代码随想录的做法吧 涉及到去重,可别忘了排序 不然去重的效果没法实现

    2024年02月16日
    浏览(42)
  • 算法刷题Day 29 递增子序列+全排列+全排列II

    如果直接像下面这样写的话,会出错,出错的案例类似: [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-9nrEEc2S-1688623883770)(LC491-递增子序列+LC.assets/image-20230703201315163.png)] 本题求自增子序列,是不能对原数组进行排序的,排完序的数组都是自增子

    2024年02月15日
    浏览(43)
  • 力扣算法刷题Day39|动态规划:不同路径 I&II

    力扣题目:#62.不同路径 刷题时长:参考题解后10min 解题方法:动规 复杂度分析 时间O(m*n) 空间O(m*n) 问题总结 初始化二维数组的python语法:i 对应 m,j 对应n 二维遍历顺序,从上到下从左到右通过两层for循环实现,其中startindex应为1 本题收获 动规思路 确定dp数组及下标的含义

    2024年02月12日
    浏览(52)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包