leetcode503. 下一个更大元素 II 单调栈

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

思路:

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

代码:

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n);
        stack<int> st;
        for (int i = 0; i < n; i++) {
            int t = nums[i];
            // 出栈并计算
            while (!st.empty() && t > nums[st.top()]) {
                int x = st.top();
                ans[x] = t;
                st.pop();
            }
            // 入栈
            while (st.empty() || (t <= nums[st.top()] && i != st.top())) {
                st.push(i);
            }
        }
        // 处理遍历完之后,栈中剩余的元素。
        while (!st.empty()) {
            int x = st.top();
            // 从头遍历数组看是否有符合要求的值。
            int i = 0;
            for (i = 0; i < n; i++) {
                if (nums[i] > nums[x]) {
                    ans[x] = nums[i];
                    break;
                }
            }
            if (i == n) ans[x] = -1;
            st.pop();
        }
        return ans;
    }
};

注意点:

for循环中的入栈出栈顺序非常重要!!!

出栈放在最后,则新元素无法入栈。

运行结果:

leetcode503. 下一个更大元素 II 单调栈,LeetCode,算法,leetcode,数据结构文章来源地址https://www.toymoban.com/news/detail-674266.html

到了这里,关于leetcode503. 下一个更大元素 II 单调栈的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【单调栈】【二分查找】LeetCode: 2454.下一个更大元素 IV

    【动态规划】【广度优先】LeetCode2258:逃离火灾 单调栈分类、封装和总结 二分查找算法合集 给你一个下标从 0 开始的非负整数数组 nums 。对于 nums 中每一个整数,你必须找到对应元素的 第二大 整数。 如果 nums[j] 满足以下条件,那么我们称它为 nums[i] 的 第二大 整数: j i n

    2024年02月03日
    浏览(42)
  • (单调栈) 496. 下一个更大元素 I——【Leetcode每日一题】

    难度:简单 nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。 给你两个 没有重复元素 的数组 nums1 和 nums2 ,下标从 0 开始计数,其中 nums1 是 nums2 的子集。 对于每个 0 = i nums1.length ,找出满足 nums1[i] == nums2[j] 的下标 j ,并且在 nums

    2024年02月08日
    浏览(40)
  • day59 | 503.下一个更大元素II、42. 接雨水

    目录: 503.下一个更大元素II https://leetcode.cn/problems/next-greater-element-ii/ 给定一个循环数组  nums  (  nums[nums.length - 1]  的下一个元素是  nums[0]  ),返回  nums  中每个元素的  下一个更大元素  。 数字  x  的  下一个更大的元素  是按数组遍历顺序,这个数字之后的第一个

    2024年02月16日
    浏览(29)
  • LeetCode每日一题 1019. 链表中的下一个更大节点 --单调栈

      Halo,这里是Ppeua。平时主要更新C语言,C++,数据结构算法......感兴趣就关注我吧!你定不会失望。 🌈个人主页:主页链接 🌈算法专栏:专栏链接       我会一直往里填充内容哒! 🌈LeetCode专栏:专栏链接       目前在刷初级算法的LeetBook 。若每日一题当中有力所能

    2024年02月01日
    浏览(63)
  • leetcode 496. 下一个更大元素 I

             这题提供暴力解法和单调栈法两种方法。         题中说了数组中没有重复的元素,为了避免重复遍历nums2数组,可以用一个哈希map和单调栈stack将nums2数组中的每个元素对应其查询值存储在map中,类似于每日温度。然后再遍历nums1查询相应元素对应的查询值。 代码

    2024年02月11日
    浏览(41)
  • 【栈】Leetcode 496 下一个更大元素I

    ---------------🎈🎈题目链接🎈🎈------------------- 两个栈进行操作,一个栈用来遍历寻找,一个栈用来保留 将待寻找的nums2中的元素入栈,之后遍历nums1, 如果栈顶元素大于nums1[i],则记录max,记录后弹出栈顶元素至tempstack,继续遍历栈,直到找到相等的为止 如果栈顶元素小于

    2024年01月17日
    浏览(39)
  • 【算法练习Day50】下一个更大元素II&&接雨水

    ​📝个人主页:@Sherry的成长之路 🏠学习社区:Sherry的成长之路(个人社区) 📖专栏链接:练题 🎯 长路漫漫浩浩,万事皆有期待 503. 下一个更大元素 II - 力扣(LeetCode) 给定一个循环数组 nums ( nums[nums.length - 1] 的下一个元素是 nums[0] ),返回 nums 中每个元素的 下一个更

    2024年01月22日
    浏览(35)
  • 算法刷题Day 59 下一个更大元素II+接雨水

    其实也可以不扩充nums,而是在遍历的过程中模拟走了两边nums 三种方法都写了一遍 暴力方法 逐列计算 找到当前位置,左边最高的柱子的索引和右边最高的柱子的索引,两者中相对小的那个,将去当前位置的高度,就是水柱的高度,而宽度是1 超时了 双指针 提前记录好左边最

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

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

    2024年02月09日
    浏览(34)
  • 【力扣】496. 下一个更大元素 I <单调栈、模拟>

      nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。给你两个没有重复元素的数组 nums1 和 nums2 ,下标从 0 开始计数,其中nums1 是 nums2 的子集。   对于每个 0 = i nums1.length ,找出满足 nums1[i] == nums2[j] 的下标 j ,并且在 nums2 确定

    2024年02月12日
    浏览(37)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包