Day58|Leetcode 739. 每日温度 Leetcode 496. 下一个更大元素 I

2023-12-21 17:36

本文主要是介绍Day58|Leetcode 739. 每日温度 Leetcode 496. 下一个更大元素 I,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Leetcode 739. 每日温度

题目链接 739 每日温度

学习单调栈,首先要明白什么时候用到单调栈,通常是一维数组,要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置,此时我们就要想到可以用单调栈了。时间复杂度为O(n)。

而针对于本题来说,单调栈里只需要存放元素的下标i就可以了,如果需要使用对应的元素,直接T[i]就可以获取。这里我们要使用递增循序(再强调一下是指从栈头到栈底的顺序),因为只有递增的时候,栈里要加入一个元素i的时候,才知道栈顶元素在数组中右面第一个比栈顶元素大的元素是i。

使用单调栈主要有三个判断条件。

  • 当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况
  • 当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况
  • 当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况

把全过程模拟一遍就可以,在对照这三种情况,就可以理解本题,下面上代码:

class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {stack<int> st;vector<int> result(temperatures.size(),0);st.push(0);for(int i=1;i<temperatures.size();i++){if(temperatures[st.top()] > temperatures[i]){st.push(i);}else if(temperatures[st.top()] == temperatures[i]){st.push(i);}else{while(!st.empty()&&temperatures[st.top()] <temperatures[i]){result[st.top()] = i-st.top();st.pop(); }st.push(i);}}return result;}
};

Leetcode 496. 下一个更大元素 I

题目链接 496 下一个更大元素 I

本题目和上面的题目差不多,这里只不过是拆成了两个数组,所以我们这里需要一个哈希映射,来找存在于num1中的和nums2中遍历元素相等的下标,我们这里用unordered_map,还需要注意一个点就是unordered_map的性质:unordered_map::count()是C++中的内置方法,如果Map中存在具有给定键的值,则此函数返回1,否则返回0。

下面上代码:

class Solution {
public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {stack<int> st;vector<int> result(nums1.size(),-1);if(nums1.size() == 0){return result;}unordered_map<int,int> umap;for(int i=0;i<nums1.size();i++){umap[nums1[i]] = i;//哈希映射,为了寻找在nums1中是否存在nums2中元素}st.push(0);for(int i=1;i<nums2.size();i++){if(nums2[i]<nums2[st.top()]){st.push(i);}else if(nums2[i] == nums2[st.top()]){st.push(i);}else{while(!st.empty()&&nums2[i]>nums2[st.top()]){if(umap.count(nums2[st.top()]) == 1){int  index = umap[nums2[st.top()]];result[index] = nums2[i];}st.pop();}st.push(i);}}return result;}
};

end,补完了有点累

这篇关于Day58|Leetcode 739. 每日温度 Leetcode 496. 下一个更大元素 I的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/520896

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return

遮罩,在指定元素上进行遮罩

废话不多说,直接上代码: ps:依赖 jquer.js 1.首先,定义一个 Overlay.js  代码如下: /*遮罩 Overlay js 对象*/function Overlay(options){//{targetId:'',viewHtml:'',viewWidth:'',viewHeight:''}try{this.state=false;//遮罩状态 true 激活,f

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎,细嗅蔷薇。你好朋友,这里是锅巴的C\C++学习笔记,常言道,不积跬步无以至千里,希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目: 牛牛发明了一种新的四舍五入应用于整数,对个位四舍五入,规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数

【JavaScript】LeetCode:16-20

文章目录 16 无重复字符的最长字串17 找到字符串中所有字母异位词18 和为K的子数组19 滑动窗口最大值20 最小覆盖字串 16 无重复字符的最长字串 滑动窗口 + 哈希表这里用哈希集合Set()实现。左指针i,右指针j,从头遍历数组,若j指针指向的元素不在set中,则加入该元素,否则更新结果res,删除集合中i指针指向的元素,进入下一轮循环。 /*** @param

学习记录:js算法(二十八):删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一:循环解法二:递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1:(图一)输入:head = [1,1,2]输出:[1,2]示例 2:(图