算法训练营第五十八天|739. 每日温度 496.下一个更大元素 I

2024-01-26 10:44

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

目录

  • Leetcode739. 每日温度
  • Leetcode496.下一个更大元素 I

Leetcode739. 每日温度

文章链接:代码随想录
题目链接:739. 每日温度

思路:暴力解法,时间超限

class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {vector<int> result(temperatures.size());for (int i = 0; i < temperatures.size(); i++){for (int j = i + 1; j < temperatures.size(); j++){if (temperatures[j] > temperatures[i]) {result[i] = j - i;break;}}}return result;}
};

单调栈,空间换时间

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

Leetcode496.下一个更大元素 I

文章链接:代码随想录
题目链接:496.下一个更大元素 I

思路:暴力解法

class Solution {
public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {vector<int> result(nums1.size(), -1);vector<int> tmp(nums1.size());for(int i = 0; i < nums1.size(); i++){for (int j = 0; j < nums2.size(); j++){if (nums1[i] == nums2[j]){tmp[i] = j;// cout << tmp[i] << endl;break;} }}for(int i = 0; i < tmp.size(); i++){for (int j = tmp[i] + 1; j < nums2.size(); j++){// cout << j << endl;if (nums2[j] > nums2[tmp[i]]) {result[i] = nums2[j];break;}}}return result;}
};

暴力解法,用umap作索引

class Solution {
public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {vector<int> result(nums1.size(), -1);unordered_map<int, int> umap;for (int i = 0; i < nums1.size(); i++){umap[nums1[i]] = i;}for (int i = 0; i < nums2.size(); i++){if (umap.count(nums2[i]) == 0) continue; for (int j = i; j < nums2.size(); j++){if (nums2[j] > nums2[i]) {result[umap[nums2[i]]] = nums2[j];break;}}}return result;}
};

单调栈,用map作索引,注意while循环的判断顺序,让是否未空先判断,避免超界运算

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

第五十八天打卡,刚才老师叫去汇报课题进度,整的在家的人有点小慌,做题有点慢,加油!!!

这篇关于算法训练营第五十八天|739. 每日温度 496.下一个更大元素 I的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

如何高效移除C++关联容器中的元素

《如何高效移除C++关联容器中的元素》关联容器和顺序容器有着很大不同,关联容器中的元素是按照关键字来保存和访问的,而顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的,本文介绍了如何高效移除C+... 目录一、简介二、移除给定位置的元素三、移除与特定键值等价的元素四、移除满足特android定条件的元

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素(即第一个元素)是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1